{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  第3章 k近邻法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 距离度量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def L(x, y, p=2):\n",
    "    # x1 = [1, 1], x2 = [5,1]\n",
    "    if len(x) == len(y) and len(x) > 1:\n",
    "        sum = 0\n",
    "        for i in range(len(x)):\n",
    "            sum += math.pow(abs(x[i] - y[i]), p)\n",
    "        return math.pow(sum, 1 / p)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 课本例3.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1 = [1, 1]\n",
    "x2 = [5, 1]\n",
    "x3 = [4, 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4.0, '1-[5, 1]')\n",
      "(4.0, '1-[5, 1]')\n",
      "(3.7797631496846193, '1-[4, 4]')\n",
      "(3.5676213450081633, '1-[4, 4]')\n"
     ]
    }
   ],
   "source": [
    "# x1, x2\n",
    "for i in range(1, 5):\n",
    "    r = {'1-{}'.format(c): L(x1, c, p=i) for c in [x2, x3]}\n",
    "    print(min(zip(r.values(), r.keys())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "python实现，遍历所有数据点，找出$n$个距离最近的点的分类情况，少数服从多数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data\n",
    "iris = load_iris()\n",
    "df = pd.DataFrame(iris.data, columns=iris.feature_names)\n",
    "df['label'] = iris.target\n",
    "df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']\n",
    "# data = np.array(df.iloc[:100, [0, 1, -1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sepal length</th>\n",
       "      <th>sepal width</th>\n",
       "      <th>petal length</th>\n",
       "      <th>petal width</th>\n",
       "      <th>label</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>145</th>\n",
       "      <td>6.7</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.2</td>\n",
       "      <td>2.3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>146</th>\n",
       "      <td>6.3</td>\n",
       "      <td>2.5</td>\n",
       "      <td>5.0</td>\n",
       "      <td>1.9</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>147</th>\n",
       "      <td>6.5</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.2</td>\n",
       "      <td>2.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>148</th>\n",
       "      <td>6.2</td>\n",
       "      <td>3.4</td>\n",
       "      <td>5.4</td>\n",
       "      <td>2.3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>149</th>\n",
       "      <td>5.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.1</td>\n",
       "      <td>1.8</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>150 rows × 5 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     sepal length  sepal width  petal length  petal width  label\n",
       "0             5.1          3.5           1.4          0.2      0\n",
       "1             4.9          3.0           1.4          0.2      0\n",
       "2             4.7          3.2           1.3          0.2      0\n",
       "3             4.6          3.1           1.5          0.2      0\n",
       "4             5.0          3.6           1.4          0.2      0\n",
       "..            ...          ...           ...          ...    ...\n",
       "145           6.7          3.0           5.2          2.3      2\n",
       "146           6.3          2.5           5.0          1.9      2\n",
       "147           6.5          3.0           5.2          2.0      2\n",
       "148           6.2          3.4           5.4          2.3      2\n",
       "149           5.9          3.0           5.1          1.8      2\n",
       "\n",
       "[150 rows x 5 columns]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x226dc21fcd0>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjcAAAGzCAYAAADT4Tb9AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy88F64QAAAACXBIWXMAAA9hAAAPYQGoP6dpAABBYUlEQVR4nO3de3RU1fn/8c8kIQloEoUaEmqAWJFbBBG0BAUvKAqKWv1a+63iDVhFoajUFsErrTZg1SLVhi/US5Eq7SKo0CJCrQlUQa6pYJBSTYAfJo0CJlwTyJzfH2MGQybDTHLOzJ6T92utWTJn9sw8Z5+D83D2PvvxWJZlCQAAwCXioh0AAACAnUhuAACAq5DcAAAAVyG5AQAArkJyAwAAXIXkBgAAuArJDQAAcBWSGwAA4CokNwAAwFVIbgAAgKskRDuAenl5eZo6daruu+8+zZw5M2CbwsJCXXbZZY22b926VT169Ajpe7xer7744gulpKTI4/G0JGQAABAhlmVp//796tSpk+Ligl+bMSK5WbdunebMmaM+ffqE1H7btm1KTU31Pz/jjDNC/q4vvvhCWVlZYccIAACib9euXTrzzDODtol6cnPgwAHdeuutmjt3rp588smQ3pOenq7TTjutWd+XkpIiydc5306QAACAuaqrq5WVleX/HQ8m6snN+PHjdc011+iKK64IObnp16+fjhw5ol69eumRRx4JOFRVr6amRjU1Nf7n+/fvlySlpqaS3AAAEGNCmVIS1eRmwYIF2rhxo9atWxdS+8zMTM2ZM0f9+/dXTU2NXnvtNQ0dOlSFhYUaMmRIwPfk5eVp2rRpdoYNAAAM5rEsy4rGF+/atUsDBgzQ8uXL1bdvX0nSpZdeqvPOO6/JCcWBjBw5Uh6PR4sXLw74+olXbuova1VVVXHlBgCAGFFdXa20tLSQfr+jdiv4hg0bVFlZqf79+yshIUEJCQkqKirSrFmzlJCQoLq6upA+Z+DAgdq+fXuTryclJfmHoBiKAgDA/aI2LDV06FBt3ry5wba77rpLPXr00OTJkxUfHx/S52zatEmZmZlOhAgAgFG8Xq9qa2ujHYZjEhMTT3qbdyiiltykpKQoJyenwbZTTjlFHTp08G+fMmWKdu/erXnz5kmSZs6cqa5du6p3796qra3V/PnzVVBQoIKCgojHDwBAJNXW1qq0tFRerzfaoTgmLi5O2dnZSkxMbNHnRP1uqWDKy8u1c+dO//Pa2lo9+OCD2r17t9q2bavevXvrb3/7m0aMGBHFKAEAcJZlWSovL1d8fLyysrJsubphmvpFdsvLy9W5c+cWLbQbtQnF0RLOhCQAAExw9OhR/ec//1GnTp2UlpYW7XAcU1VVpS+++EJnn3222rRp0+C1mJhQDAAAQlN/k01Lh2tMV79/od5U1BSSGwAAYoTbayLatX9Gz7kBADvVeS2tLd2ryv1HlJ6SrAuz2ys+zt0/FkBrRHIDoFVYtqVc05aUqLzqiH9bZlqyHh/ZS1fnsJwE4CYMSwFwvWVbynXP/I0NEhtJqqg6onvmb9SyLeVRigxoHX7/+98rOztbycnJ6t+/v1atWuXo95HcAHC1Oq+laUtKFOi20Ppt05aUqM7bqm4cRStV57W0+rM9ert4t1Z/tici5/2f//xn3X///Xr44Ye1adMmDR48WMOHD2+w1IvdGJYC4GprS/c2umLzbZak8qojWlu6V7nf6xC5wIAIi9bQ7HPPPafRo0drzJgxknwL8r777rvKz89XXl6eI9/JlRsArla5v+nEpjntgFgUraHZ2tpabdiwQcOGDWuwfdiwYfrwww8d+U6J5AaAy6WnJNvaDog10Rya/eqrr1RXV6eOHTs22N6xY0dVVFTY/n31SG4AuNqF2e2VmZaspm749sh3af7C7PaRDAuImHCGZp1y4vo1lmU5umYPyQ0AV4uP8+jxkb0kqVGCU//88ZG9WO8GrhXNodnvfOc7io+Pb3SVprKystHVHDuR3ABwvatzMpV/2/nKSGs49JSRlqz8285nnRu4WjSHZhMTE9W/f3+tWLGiwfYVK1Zo0KBBtn9fPe6WAtAqXJ2TqSt7ZbBCMVqd+qHZiqojAefdeORL9J0amp00aZJGjRqlAQMGKDc3V3PmzNHOnTs1btw4R75PIrkB0IrEx3m43RutTv3Q7D3zN8ojNUhwIjE0e8stt2jPnj365S9/qfLycuXk5Gjp0qXq0qWLI98nMSwFAIDrRXto9t5771VZWZlqamq0YcMGDRkyxNHv48oNAACtQGsamiW5AQCglWgtQ7MMSwEAAFchuQEAAK5CcgMAAFyF5AYAALgKyQ0AAHAVkhsAAOAqJDcAAMBVSG4AAICrkNwAAADHrFy5UiNHjlSnTp3k8Xj01ltvOf6dJDcAALQW3jqpdJW0eaHvv946x7/y4MGD6tu3r1544QXHv6se5RcAAGgNShZLyyZL1V8c35baSbp6htTrOse+dvjw4Ro+fLhjnx8IV24AAHC7ksXSX25vmNhIUnW5b3vJ4ujE5RCSGwAA3Mxb57tiIyvAi99sW/ZQRIaoIoXkBoDj6ryWVn+2R28X79bqz/aozhvof7IAHLHjw8ZXbBqwpOrdvnYuwZwbAI5atqVc05aUqLzqiH9bZlqyHh/ZS1fnZEYxMqCVOPBfe9vFAK7cAHDMsi3lumf+xgaJjSRVVB3RPfM3atmW8ihFBrQip3a0t10MILkB4Ig6r6VpS0qCjfJr2pIShqgAp3UZ5LsrSp4mGnik1O/62jngwIEDKi4uVnFxsSSptLRUxcXF2rlzpyPfJ5HcAHDI2tK9ja7YfJslqbzqiNaW7o1cUEBrFBfvu91bUuME55vnV0/3tXPA+vXr1a9fP/Xr10+SNGnSJPXr10+PPfaYI98nMecGgEMq9zed2DSnHYAW6HWd9MN5TaxzM93RdW4uvfRSWVZkr9CS3ABwRHpKsq3tALRQr+ukHtf47oo68F/fHJsugxy7YhNNJDcAHHFhdntlpiWroupIwHk3HkkZacm6MLt9pEMDWq+4eCl7cLSjcBxzbgA4Ij7Oo8dH9pLU5Ci/Hh/ZS/FxTU1yBIDmIbkB4JirczKVf9v5ykhrOPSUkZas/NvOZ50bAI5gWAqAo67OydSVvTK0tnSvKvcfUXqKbyiKKzZA+CI9MTfS7No/khsAjouP8yj3ex2iHQYQs+LjfZN+a2tr1bZt2yhH45za2lpJx/e3uUhuAAAwXEJCgtq1a6cvv/xSbdq0UVyc+2aVeL1effnll2rXrp0SElqWnpDcAABgOI/Ho8zMTJWWlmrHjh3RDscxcXFx6ty5szyelg1bk9wABqvzWsxVASBJSkxMVLdu3fxDN26UmJhoy1UpkhvAUFTTBnCiuLg4JSez8OXJuG/QDnABqmkDQPOR3ACGoZo2ALQMyQ1gGKppA0DLkNwAhqGaNgC0DMkNYBiqaQNAy5DcAIapr6bd1A3fHvnumqKaNgAERnIDGIZq2gDQMiQ3gIGopg0AzccifoChqKYNAM1DcgMYjGraABA+hqUAAICrkNwAAABXYVgKAEJElXYgNhhz5SYvL08ej0f3339/0HZFRUXq37+/kpOTddZZZ2n27NmRCRBAq7ZsS7kunvEP/e/cNbpvQbH+d+4aXTzjHxQxBQxkRHKzbt06zZkzR3369AnarrS0VCNGjNDgwYO1adMmTZ06VRMnTlRBQUGEIgXQGlGlHYgtUU9uDhw4oFtvvVVz587V6aefHrTt7Nmz1blzZ82cOVM9e/bUmDFjdPfdd+uZZ56JULQAWhuqtAOxJ+rJzfjx43XNNdfoiiuuOGnb1atXa9iwYQ22XXXVVVq/fr2OHj0a8D01NTWqrq5u8ACAUFGlHYg9UU1uFixYoI0bNyovLy+k9hUVFerYsWODbR07dtSxY8f01VdfBXxPXl6e0tLS/I+srKwWxw2g9aBKOxB7opbc7Nq1S/fdd5/mz5+v5OTQqxt7PA3vTLAsK+D2elOmTFFVVZX/sWvXruYHDaDVoUo7EHuidiv4hg0bVFlZqf79+/u31dXVaeXKlXrhhRdUU1Oj+Pj4Bu/JyMhQRUVFg22VlZVKSEhQhw6BV3FNSkpSUlKS/TsAoFWor9JeUXUk4Lwbj3w1v6jSDpgjalduhg4dqs2bN6u4uNj/GDBggG699VYVFxc3SmwkKTc3VytWrGiwbfny5RowYIDatGkTqdABtCJUaQdiT9SSm5SUFOXk5DR4nHLKKerQoYNycnIk+YaUbr/9dv97xo0bpx07dmjSpEnaunWrXn75Zb300kt68MEHo7UbAFoBqrQDscXoFYrLy8u1c+dO//Ps7GwtXbpUDzzwgF588UV16tRJs2bN0k033RTFKAG0BlRpB2KHx6qfkdtKVFdXKy0tTVVVVUpNTY12OAAAIATh/H5HfZ0bAAAAO5HcAAAAVzF6zg0AM9Qe8+q11WXasfeQurRvp1G5XZWYwL+NAJiJ5AZAUHlLSzR3Vam+XTrpqaVbNXZwtqaM6BW9wACgCSQ3AJqUt7RE/7eytNF2ryX/dhIcAKbhujKAgGqPeTV3VePE5tvmripV7TFvhCICgNCQ3AAI6LXVZQ2GogLxWr52AGASkhsAAe3Ye8jWdgAQKSQ3AALq0r6dre0AIFJIbgAENCq3q05WWSDO42sHACYhuQEQUGJCnMYOzg7aZuzgbNa7AWAcbgUH0KT627xPXOcmziPWuQFgLApnAjgpVigGEG3h/H5z5QbASSUmxGn04LOiHQYAhIR/egEAAFchuQEAAK7CsBTgoMO1dfr10hKV7Tmkrh3aaeqIXmqbGB/tsFqtOq+ltaV7Vbn/iNJTknVhdnvFn+x+dwAxh+QGcMjYeeu0oqTS/3zVdum1NTt1Za90zb39gihG1jot21KuaUtKVF51xL8tMy1Zj4/spatzMqMYGQC7MSwFOODExObbVpRUauy8dRGOqHVbtqVc98zf2CCxkaSKqiO6Z/5GLdtSHqXIADiB5Aaw2eHauiYTm3orSip1uLYuQhG1bnVeS9OWlCjQmhf126YtKVHdyaqEAogZJDeAzX69tMTWdmiZtaV7G12x+TZLUnnVEa0t3Ru5oAA4iuQGsFnZntCqZIfaDi1Tub/pxKY57QCYj+QGsFnXDqFVyQ61HVomPSXZ1nYAzEdyA9hsaoj1lkJth5a5MLu9MtOS1dQN3x757pq6MLt9JMMC4CCSG8BmbRPjdWWv9KBtruyVzno3ERIf59HjI32J5IkJTv3zx0f2Yr0bwEVIbgAHzL39giYTHNa5ibyrczKVf9v5ykhrOPSUkZas/NvOZ50bwGWoCg44iBWKzcIKxUDsCuf3m+QGAAAYL5zfb4alAACAq5DcAAAAV6FwJuAgE+Z42BGDCfsBAKEiuQEcYkIVajtiMGE/ACAcDEsBDjChCrUdMZiwHwAQLpIbwGYmVKG2IwYT9gMAmoPkBrCZCVWo7YjBhP0AgOYguQFsZkIVajtiMGE/AKA5SG4Am5lQhdqOGEzYDwBoDpIbwGYmVKG2IwYT9gMAmoPkBrCZCVWo7YjBhP0AgOYguQEcYEIVajtiMGE/ACBcFM4EHGTCyr6sUAzADcL5/WaFYsBB8XEe5X6vQ8zHYMJ+AECoGJYCAACuQnIDAABchWEpNOCWuRXMMwGA1ovkBn5uqf5MJWwAaN0YloIk91R/phI2AIDkBq6p/kwlbACARHIDuaf6M5WwAQASyQ3knurPVMIGAEgkN5B7qj9TCRsAIJHcQO6p/kwlbACARHIDuaf6M5WwAQASyQ2+4Zbqz1TCBgBQFRwNuGVVXlYoBgB3oSo4ms0t1Z+phA0ArRfDUgAAwFVIbgAAgKswLAU0ofaYV6+tLtOOvYfUpX07jcrtqsSE8P490NLPcMu8H7fsB4DYENUJxfn5+crPz1dZWZkkqXfv3nrsscc0fPjwgO0LCwt12WWXNdq+detW9ejRI6TvZEIxQpG3tERzV5Xq2yWk4jzS2MHZmjKiV0Q+wy2Vyd2yHwCiK5zf76gOS5155pmaPn261q9fr/Xr1+vyyy/X9ddfr08++STo+7Zt26by8nL/o1u3bhGKGK1B3tIS/d/KhkmJJHkt6f9WlipvaYnjn+GWyuRu2Q8AsSWqyc3IkSM1YsQInXPOOTrnnHP01FNP6dRTT9WaNWuCvi89PV0ZGRn+R3x8fIQihtvVHvNq7qrSoG3mripV7TGvY5/hlsrkbtkPALHHmAnFdXV1WrBggQ4ePKjc3Nygbfv166fMzEwNHTpU77//ftC2NTU1qq6ubvAAmvLa6rJGV1tO5LV87Zz6DLdUJnfLfgCIPVFPbjZv3qxTTz1VSUlJGjdunN5880316hV4PkJmZqbmzJmjgoICLVq0SN27d9fQoUO1cuXKJj8/Ly9PaWlp/kdWVpZTuwIX2LH3UIvbtfQz3FKZ3C37ASD2RP1uqe7du6u4uFhff/21CgoKdMcdd6ioqChggtO9e3d1797d/zw3N1e7du3SM888oyFDhgT8/ClTpmjSpEn+59XV1SQ4aFKX9u1a3K6ln+GWyuRu2Q8AsSfqV24SExN19tlna8CAAcrLy1Pfvn31/PPPh/z+gQMHavv27U2+npSUpNTU1AYPoCmjcrvqZHcox3l87Zz6DLdUJnfLfgCIPVFPbk5kWZZqampCbr9p0yZlZnI7KeyRmBCnsYOzg7YZOzg76Fo1Lf0Mt1Qmd8t+AIg9zRqWeu+99/Tee++psrJSXm/DOz5efvnlkD9n6tSpGj58uLKysrR//34tWLBAhYWFWrZsmSTfkNLu3bs1b948SdLMmTPVtWtX9e7dW7W1tZo/f74KCgpUUFDQnN0AAqpfg6Yla9S09DPqK5OfuD5MRoytD+OW/QAQW8JObqZNm6Zf/vKXGjBggDIzM+XxNP9fXf/97381atQolZeXKy0tTX369NGyZct05ZVXSpLKy8u1c+dOf/va2lo9+OCD2r17t9q2bavevXvrb3/7m0aMGNHsGIBApozopZ8N69Gi1YVb+hlX52Tqyl4ZMb+yr1v2A0DsCHuF4szMTD399NMaNWqUUzE5ihWKAQCIPY6uUFxbW6tBgwY1OzgAAAAnhZ3cjBkzRq+//roTsQAAALRYSHNuvr1OjNfr1Zw5c/T3v/9dffr0UZs2bRq0fe655+yNEBFlQvVmO6pxmxJHS/vThOMhmXNM8A1vnbTjQ+nAf6VTO0pdBklxlKEB6oU05yZQJe6mnKwcQrQx56ZpJlRvtqMatylxtLQ/TTgekjnHBN8oWSwtmyxVf3F8W2on6eoZUq/rohcX4LBwfr/DnlAc60huAquv3nziyVB/jSD/tvMd/0Gtr6TdlJ8MicyPqR1xtLQ/TTgekjnHBN8oWSz95XapqTPjh/NIcOBajk4ovvvuu7V///5G2w8ePKi777473I+DAUyo3mxHNW5T4mhpf5pwPCRzjgm+4a3zXbEJdmYse8jXDmjlwk5u/vjHP+rw4cONth8+fNi/2B5iiwnVm+2oxm1KHC3tTxOOh2TOMcE3dnzYcCiqEUuq3u1rB7RyIS/iV11dLcuyZFmW9u/fr+Tk48Xu6urqtHTpUqWnpzsSJJxlQvVmO6pxmxJHS/vThOMhmXNM8I0D/7W3HeBiISc3p512mjwejzwej84555xGr3s8Hk2bNs3W4BAZJlRvtqMatylxtLQ/TTgekjnHBN84taO97QAXCzm5ef/992VZli6//HIVFBSoffvjlXwTExPVpUsXderUyZEg4az66s0VVUcCjuZ75KsF5GT15lG5XfXU0q1Bh0FOVo3blDha2p8mHA/JnGOCb3QZ5LsrqrpcgefdeHyvd2GRVSDkOTeXXHKJLr30UpWWluqGG27QJZdc4n/k5uaS2MQwE6o321GN25Q4WtqfJhwPyZxjgm/Exftu95bU5Jlx9XTWuwEU4q3gH3/8ccgf2KdPnxYF5DRuBW+aCeuqmLKmCuvcHGfKMcE3Aq5z811fYsNt4HAx29e5iYuLk8fjkWVZJ60CXldn9m2IJDfBmbAirimr4bJC8XGmHBN8gxWK0QrZntzs2LHD/+dNmzbpwQcf1M9//nPl5uZKklavXq1nn31WTz/9tG644YaWRe8wkhsAAGJPOL/fIU0o7tKli//PN998s2bNmqURI0b4t/Xp00dZWVl69NFHjU9uAACAu4V9XXnz5s3Kzm48yTA7O1slJSW2BAUAANBcYSc3PXv21JNPPqkjR45PcqypqdGTTz6pnj172hocEE11XkurP9ujt4t3a/Vne5pV7sCOzwBcy1snla6SNi/0/ZfSEbBJyOvc1Js9e7ZGjhyprKws9e3bV5L0r3/9Sx6PR3/9619tDxCIBjvuVDLlbifASFQ3h4OaVRX80KFDmj9/vj799FNZlqVevXrpxz/+sU455RQnYrQVE4pxMnZU5DalqjdgJKqboxlsv1vKTUhuEEyd19LFM/7RZOHK+tWB/zn58iZvybbjMwDX8tZJM3OCFAH9ZqXl+zdzezsasP1uqcWLF2v48OFq06aNFi9eHLTtddeRbSN2hVORO/d7HRz7DMC1wqlunj04YmHBXUJKbm644QZVVFQoPT096K3eHo/H+EX8gGDsqMhtSlVvwEhUN0cEhJTceL3egH8G3MaOitymVPUGjER1c0RA2LeCHzp0yIk4ACPUV+RuaiaMR747noJV5LbjMwDXqq9uHuxvSOp3qW6OFgk7uTnttNM0aNAgTZ06Ve+++64OHjzoRFxAVNhRkduUqt6AkahujggIO7kpKirSddddp40bN+rmm2/W6aefroEDB+qhhx7SO++840SMQERdnZOp/NvOV0Zaw2GjjLTkkG/htuMzANfqdZ3vdu/UE/4epHbiNnDYokW3gtfV1WndunWaPXu2/vSnP8nr9Ro/oZhbwREqOypym1LVGzAS1c0RBttvBT/Rp59+qsLCQhUVFamwsFBHjx7VyJEjdckllzQrYMBE8XGeFt+qbcdnAK4VF8/t3nBE2MlNRkaGjh49qssvv1yXXnqppk6dqnPPPdeJ2AAAAMIW9pybjIwMHThwQDt37tTOnTv1//7f/9OBAweciA0AACBsYV+5KS4u1tdff62VK1eqqKhIjz76qD755BP16dNHl112maZPn+5EnK2CCfMz7Iih9phXr60u0469h9SlfTuNyu2qxISw8+ioM+F4wIWYZ2Iv+tMshhyPFk0o3rt3rwoLC/X222/r9ddfZ0JxC5hQQdqOGPKWlmjuqlJ5v3VWxXmksYOzNWVEL7tDdowJxwMuRCVse9GfZnH4eDhaOPPNN99UYWGhCgsL9cknn6hDhw4aPHiwLr30Ul122WXq3bt3i4J3monJjQkVpO2IIW9pif5vZWmTr/9kSGwkOCYcD7gQlbDtRX+aJQLHw9HkJj09XUOGDNGll16qSy+9VDk5OS0KNtJMS25MqCBtRwy1x7zq8eg7Da7YnCjOI336q+FGD1GZcDzgQlTCthf9aZYIHY9wfr/D/pWprKzUwoULNWHChJhLbEwUTgVpk2N4bXVZ0MRGkryWr53JTDgecKFwKmHj5OhPsxh4PMz9J3QrYUIFaTti2LE3tJpjobaLFhOOB1yIStj2oj/NYuDxILmJMhMqSNsRQ5f27UL6jFDbRYsJxwMuRCVse9GfZjHweJDcRJkJFaTtiGFUbledbApKnMfXzmQmHA+4EJWw7UV/msXA40FyE2UmVJC2I4bEhDiNHZwd9HvGDs42ejKxZMbxgAtRCdte9KdZDDweZv/StBImVJC2I4YpI3rpJ0OyG13BifPEzm3gkhnHAy5EJWx70Z9mMex4hHQr+I033hjyBy5atKhFATnNtFvBv82EFXFZofg4E44HXMiQFVxdg/40i4PHw/aq4GlpabYEhuBMqCBtRwyJCXEaPfgsmyKKHhOOB1yIStj2oj/NYsjxCCm5eeWVV5yOAwAAwBaxN1YAAAAQRNhVwSVp4cKF+stf/qKdO3eqtra2wWsbN260JTBEhwnzTJj3A6DVOVYrrZsr7SuTTu8qXTBWSkiMbAwumr8UdnIza9YsPfzww7rjjjv09ttv66677tJnn32mdevWafz48U7EiAgxoRK2U5XJn1q6NeYqkwNoJZY/Kq1+QbK839r2iJQ7QRr2q8jE4LIK62EXzuzRo4cef/xx/e///q9SUlL0r3/9S2eddZYee+wx7d27Vy+88IJTsdrC5LulosmESthUJgfQ6ix/VPpwVtOvD5rofIITIxXWHS2cuXPnTg0a5FtlsG3bttq/f78kadSoUXrjjTeaES6irc5radqSkkantXT8VJ+2pER1J6uMGeUYao95NXdV04mNJM1dVaraY96gbQAgIo7V+q7YBLP6RV87p3jrfFdsgv3fd9lDvnYxJOzkJiMjQ3v27JEkdenSRWvWrJEklZaWKsyLQDCECZWwqUwOoNVZN7fhUFQgVp2vnVMMrOhth7CTm8svv1xLliyRJI0ePVoPPPCArrzySt1yyy36wQ9+YHuAcJ4JlbCpTA6g1dlXZm+75jCworcdwp5QPGfOHHm9vkxz3Lhxat++vf75z39q5MiRGjdunO0BwnkmVMKmMjmAVuf0rva2aw4DK3rbIewrN3FxcUpIOJ4T/fCHP9SsWbM0ceJEJSZG+LY12MKESthUJgfQ6lwwVvKc5GfYE+9r5xQDK3rboVkLf+zbt0/PPPOMRo8erTFjxujZZ5/V3r3OzceAs0yohE1lcgCtTkKi73bvYHLHO7vejYEVve0Q9v/li4qKlJ2drVmzZmnfvn3au3evZs2apezsbBUVFTkRIyLAhErYVCYH0OoM+5Xvdu8Tr+B44iNzG7hkXEVvO4S9zk1OTo4GDRqk/Px8xcf7Mrm6ujrde++9+uCDD7RlyxZHArUL69wExwrFABAFrFB8UuH8foed3LRt21bFxcXq3r17g+3btm3Teeedp8OHD4cfcQSR3AAAEHscXcTv/PPP19atWxtt37p1q84777xwPw4AAMBWYd8KPnHiRN133336z3/+o4EDB0qS1qxZoxdffFHTp0/Xxx9/7G/bp08f+yIFAAAIQdjDUnFxwS/2eDweWZYlj8ejujrzlmt2aljKjnkiJsx3MYEd82U4HjYzYSzejjkJJuyHCTGYFIcb2NGXHI+TCuf3O+wrN6WlwWv3hCM/P1/5+fkqKyuTJPXu3VuPPfaYhg8f3uR7ioqKNGnSJH3yySfq1KmTfvGLX0R98UA7KlmbUJHbBHZU9OZ42MyEasF2VE02YT9MiMGkONzAjr7keNgu7Cs3dlqyZIni4+N19tlnS5L++Mc/6je/+Y02bdqk3r17N2pfWlqqnJwcjR07Vj/5yU/0wQcf6N5779Ubb7yhm266KaTvtPvKjR2VrE2oyG0COyp6czxsZkK1YDuqJpuwHybEYFIcbmBHX3I8QubohGJJeu2113TRRRepU6dO2rFjhyRp5syZevvtt8P6nJEjR2rEiBE655xzdM455+ipp57Sqaee6i/GeaLZs2erc+fOmjlzpnr27KkxY8bo7rvv1jPPPNOc3WgxOypZm1CR2wR2VPTmeNjMhGrBdlRNNmE/TIjBpDjcwI6+5Hg4JuzkJj8/X5MmTdKIESP09ddf++fVnHbaaZo5c2azA6mrq9OCBQt08OBB5ebmBmyzevVqDRs2rMG2q666SuvXr9fRo0cDvqempkbV1dUNHnaxo5K1CRW5TWBHRW+Oh81MqBZsR9VkE/bDhBhMisMN7OhLjodjwk5ufve732nu3Ll6+OGH/Yv4SdKAAQO0efPmsAPYvHmzTj31VCUlJWncuHF688031atX4KGHiooKdezYsHhXx44ddezYMX311VcB35OXl6e0tDT/IysrK+wYm2JHJWsTKnKbwI6K3hwPm5lQLdiOqskm7IcJMZgUhxvY0ZccD8eEndyUlpaqX79+jbYnJSXp4MGDYQfQvXt3FRcXa82aNbrnnnt0xx13qKSkpMn2Hk/Du1XqpwyduL3elClTVFVV5X/s2rUr7BibYkclaxMqcpvAjoreHA+bmVAt2I6qySbshwkxmBSHG9jRlxwPx4Sd3GRnZ6u4uLjR9nfeeafJKy7BJCYm6uyzz9aAAQOUl5envn376vnnnw/YNiMjQxUVFQ22VVZWKiEhQR06dAj4nqSkJKWmpjZ42MWOStYmVOQ2gR0VvTkeNjOhWrAdVZNN2A8TYjApDjewoy85Ho4JO7n5+c9/rvHjx+vPf/6zLMvS2rVr9dRTT2nq1Kn6+c9/3uKALMtSTU1NwNdyc3O1YsWKBtuWL1+uAQMGqE2bNi3+7nDZUcnahIrcJrCjojfHw2YmVAu2o2qyCfthQgwmxeEGdvQlx8MxYSc3d911lx5//HH94he/0KFDh/TjH/9Ys2fP1vPPP68f/ehHYX3W1KlTtWrVKpWVlWnz5s16+OGHVVhYqFtvvVWSb0jp9ttv97cfN26cduzYoUmTJmnr1q16+eWX9dJLL+nBBx8MdzdsY0claxMqcpvAjoreHA+bmVAt2I6qySbshwkxmBSHG9jRlxwPR7RonZuvvvpKXq9X6enpzXr/6NGj9d5776m8vFxpaWnq06ePJk+erCuvvFKSdOedd6qsrEyFhYX+9xQVFemBBx7wL+I3efLksBbxY4Vi87FCsYFMWD2VFYrdGYcbsEJxRDhaFfzw4cOyLEvt2vkmdu7YscN/h9OJt2mbiKrgAADEHkcX8bv++us1b948SdLXX3+tCy+8UM8++6yuv/565efnNy9iAAAAm4Sd3GzcuFGDBw+WJC1cuFAZGRnasWOH5s2bp1mzgiyRDgAAEAFhF848dOiQUlJSJPnuVLrxxhsVFxengQMH+ksxoHmY4wEEwbyG40zoC1P60oQ4TIgBDYSd3Jx99tl666239IMf/EDvvvuuHnjgAUm+9WaYw9J8VKEGgqDy8nEm9IUpfWlCHCbEgEbCnlC8cOFC/fjHP1ZdXZ2GDh2q5cuXS/KVOVi5cqXeeecdRwK1i4kTiqlCDQRB5eXjTOgLU/rShDhMiKEVcfRuKclX46m8vFx9+/ZVXJxv2s7atWuVmpqqHj16NC/qCDEtuanzWrp4xj+aLNbokW99lX9OvpwhKrQ+3jppZk6Q4oIe37+S79/c9DCAHZ9hAhP6wpS+NCEOE2JoZRy9W0rylUHo16+fP7GRpAsvvND4xMZEVKEGgqDy8nEm9IUpfWlCHCbEgCY1K7mBfahCDQRB5eXjTOgLU/rShDhMiAFNIrmJMqpQA0FQefk4E/rClL40IQ4TYkCTSG6ijCrUQBBUXj7OhL4wpS9NiMOEGNAkkpsoowo1EASVl48zoS9M6UsT4jAhBjSJ5MYAVKEGgqDy8nEm9IUpfWlCHCbEgIBaVBU8Fpl2K/i3sUIxEIQJq/KawoS+MKUvTYjDhBhaAcfXuYllJic3AAAgMMfXuQEAADAVyQ0AAHCVsAtnAkDMOlYrrZsr7SuTTu8qXTBWSkiMdlTRQV/4uGW+jFv2wybMuQHQOix/VFr9gmR5j2/zxEm5E6Rhv4peXNFAX/i4paK3W/bjJJhzAwDftvxR6cNZDX/MJd/zD2f5Xm8t6Auf+oreJ9aHqi73bS9ZHJ24wuWW/bAZyQ0AdztW67tKEczqF33t3I6+8PHW+a50KNDAxTfblj3ka2cyt+yHA0huALjburmNr1KcyKrztXM7+sLHLRW93bIfDiC5AeBu+8rsbRfL6Asft1T0dst+OIDkBoC7nd7V3naxjL7wcUtFb7fshwNIbgC42wVjfXcCBeOJ97VzO/rCxy0Vvd2yHw4guQHgbgmJvlucg8kd3zrWeKEvfNxS0dst++EAkhsA7jfsV9KgiY2vWnjifdtb09ou9IWPWyp6u2U/bMYifgBaD1blPY6+8HHLyr5u2Y8gqAoeBMkNAACxhxWKAQBAq0VyAwAAXIWq4IDJWsE4eshM6AtT5qmY0BeAwUhuAFO1kkq/ITGhLwJV0l7+SOQraZvQF4DhGJYCTESl3+NM6AtTKmmb0BdADCC5AUxDpd/jTOgLUyppm9AXQIwguQFMQ6Xf40zoC1MqaZvQF0CMILkBTEOl3+NM6AtTKmmb0BdAjCC5AUxDpd/jTOgLUyppm9AXQIwguQFMQ6Xf40zoC1MqaZvQF0CMILkBTEOl3+NM6AtTKmmb0BdAjCC5AUxEpd/jTOgLUyppm9AXQAygcCZgMlaiPc6EvmCFYiBqqAoeBMkNAACxh6rgAACg1SK5AQAArkLhTADOM2WOSEvjMGU/AARFcgPAWaZUsW5pHKbsB4CTYlgKgHNMqWLd0jhM2Q8AISG5AeAMU6pYtzQOU/YDQMhIbgA4w5Qq1i2Nw5T9ABAykhsAzjClinVL4zBlPwCEjOQGgDNMqWLd0jhM2Q8AISO5AeAMU6pYtzQOU/YDQMhIbgA4w5Qq1i2Nw5T9ABAykhsAzjGlinVL4zBlPwCEhMKZAJxnysq+rFAMxKxwfr9ZoRiA8+LipezB0Y6i5XGYsh8AgmJYCgAAuArJDQAAcBWGpQAnMUfDx45+oC/dh2MKh0Q1ucnLy9OiRYv06aefqm3btho0aJBmzJih7t27N/mewsJCXXbZZY22b926VT169HAyXCA8VJH2saMf6Ev34ZjCQVEdlioqKtL48eO1Zs0arVixQseOHdOwYcN08ODBk75327ZtKi8v9z+6desWgYiBEFFF2seOfqAv3YdjCocZdSv4l19+qfT0dBUVFWnIkCEB29Rfudm3b59OO+20sL+DW8HhOG+dNDMnSLFFj+9fqPdvdvcleDv6gb50H44pmimc32+jJhRXVVVJktq3b3/Stv369VNmZqaGDh2q999/v8l2NTU1qq6ubvAAHEUVaR87+oG+dB+OKSLAmOTGsixNmjRJF198sXJycppsl5mZqTlz5qigoECLFi1S9+7dNXToUK1cuTJg+7y8PKWlpfkfWVlZTu0C4EMVaR87+oG+dB+OKSLAmLulJkyYoI8//lj//Oc/g7br3r17gwnHubm52rVrl5555pmAQ1lTpkzRpEmT/M+rq6tJcOAsqkj72NEP9KX7cEwRAUZcufnpT3+qxYsX6/3339eZZ54Z9vsHDhyo7du3B3wtKSlJqampDR6Ao6gi7WNHP9CX7sMxRQRENbmxLEsTJkzQokWL9I9//EPZ2dnN+pxNmzYpMzPz5A2BSKCKtI8d/UBfug/HFBEQ1eRm/Pjxmj9/vl5//XWlpKSooqJCFRUVOnz4sL/NlClTdPvtt/ufz5w5U2+99Za2b9+uTz75RFOmTFFBQYEmTJgQjV0AAqOKtI8d/UBfug/HFA6L6q3gHk/gy5KvvPKK7rzzTknSnXfeqbKyMhUWFkqSnn76ac2ZM0e7d+9W27Zt1bt3b02ZMkUjRowI6Tu5FRwRxQqsPqxQjEA4pghDOL/fRq1zEwkkNwAAxJ6YXecGAACgpUhuAACAqxizzg1gK8byzXKsVlo3V9pXJp3eVbpgrJSQGO2oALgUyQ3ch2rDZln+qLT6BcnyfmvbI1LuBGnYr6IXFwDXYlgK7kK1YbMsf1T6cFbDxEbyPf9wlu91ALAZyQ3cw1vnu2KjQDcAfrNt2UO+dnDesVrfFZtgVr/oawcANiK5gXtQbdgs6+Y2vmJzIqvO1w4AbERyA/eg2rBZ9pXZ2w4AQkRyA/eg2rBZTu9qbzsACBHJDdyDasNmuWCs5DnJ/2I88b52AGAjkhu4B9WGzZKQ6LvdO5jc8ax3A8B2JDdwF6oNm2XYr6RBExtfwfHE+7azzg0AB1A4E+7ECsVmYYViAC0Uzu83KxTDneLipezB0Y4C9RISfUNQABABDEsBAABXIbkBAACuwrCUi9R5La0t3avK/UeUnpKsC7PbKz6uqduicVLM27EPfYlAOC/gEJIbl1i2pVzTlpSovOqIf1tmWrIeH9lLV+dkBnknAqKyuH3oSwTCeQEHMSzlAsu2lOue+RsbJDaSVFF1RPfM36hlW8qjFFmMorK4fehLBMJ5AYeR3MS4Oq+laUtKgtXB1rQlJarztqo7/puPyuL2oS8RCOcFIoDkJsatLd3b6IrNt1mSyquOaG3p3sgFFcuoLG4f+hKBcF4gAkhuYlzl/qYTm+a0a/WoLG4f+hKBcF4gAkhuYlx6SrKt7Vo9Kovbh75EIJwXiACSmxh3YXZ7ZaYlB6uDrcw0323hCAGVxe1DXyIQzgtEAMlNjIuP8+jxkb0kNVkHW4+P7MV6N6Gisrh96EsEwnmBCCC5cYGrczKVf9v5ykhrOPSUkZas/NvOZ52bcFFZ3D70JQLhvIDDqAruIqxQbDNWT7UPfYlAOC8QhnB+v0luAACA8cL5/WZYCgAAuArJDQAAcBUKZwJArDFhrooJMQBNILkBgFhiQjVtE2IAgmBYCgBihQnVtE2IATgJkhsAiAUmVNM2IQYgBCQ3ABALTKimbUIMQAhIbgAgFphQTduEGIAQkNwAQCwwoZq2CTEAISC5AYBYYEI1bRNiAEJAcgMAscCEatomxACEgOQGAGKFCdW0TYgBOAkKZwJArDFhdWATYkCrEs7vNysUA0CsiYuXsgcTA9AEhqUAAICrkNwAAABXIbkBAACuQnIDAABcheQGAAC4CskNAABwFZIbAADgKiQ3AADAVUhuAACAq5DcAAAAVyG5AQAArkJyAwAAXIXkBgAAuArJDQAAcBWSGwAA4CokNwAAwFUSoh0AYCxvnbTjQ+nAf6VTO0pdBklx8dGOCgBwElG9cpOXl6cLLrhAKSkpSk9P1w033KBt27ad9H1FRUXq37+/kpOTddZZZ2n27NkRiBatSsliaWaO9MdrpYLRvv/OzPFtBwAYLarJTVFRkcaPH681a9ZoxYoVOnbsmIYNG6aDBw82+Z7S0lKNGDFCgwcP1qZNmzR16lRNnDhRBQUFEYwcrlayWPrL7VL1Fw23V5f7tpPgAIDRPJZlWdEOot6XX36p9PR0FRUVaciQIQHbTJ48WYsXL9bWrVv928aNG6d//etfWr169Um/o7q6WmlpaaqqqlJqaqptscMlvHW+KzQnJjZ+Him1k3T/ZoaoACCCwvn9NmpCcVVVlSSpffv2TbZZvXq1hg0b1mDbVVddpfXr1+vo0aON2tfU1Ki6urrBA2jSjg+DJDaSZEnVu33tAABGMia5sSxLkyZN0sUXX6ycnJwm21VUVKhjx44NtnXs2FHHjh3TV1991ah9Xl6e0tLS/I+srCzbY4eLHPivve0AABFnTHIzYcIEffzxx3rjjTdO2tbj8TR4Xj+yduJ2SZoyZYqqqqr8j127dtkTMNzp1I4nbxNOOwBAxBlxK/hPf/pTLV68WCtXrtSZZ54ZtG1GRoYqKioabKusrFRCQoI6dOjQqH1SUpKSkpJsjRcu1mWQb05NdbmkQNPRvplz02VQpCMDAIQoqlduLMvShAkTtGjRIv3jH/9Qdnb2Sd+Tm5urFStWNNi2fPlyDRgwQG3atHEqVLQWcfHS1TO+eXLilcBvnl89ncnEAGCwqCY348eP1/z58/X6668rJSVFFRUVqqio0OHDh/1tpkyZottvv93/fNy4cdqxY4cmTZqkrVu36uWXX9ZLL72kBx98MBq7ADfqdZ30w3lSambD7amdfNt7XReduAAAIYnqreCB5shI0iuvvKI777xTknTnnXeqrKxMhYWF/teLior0wAMP6JNPPlGnTp00efJkjRs3LqTv5FZwhIwVigHAGOH8fhu1zk0kkNwAABB7YnadGwAAgJYiuQEAAK5CcgMAAFyF5AYAALgKyQ0AAHAVkhsAAOAqJDcAAMBVSG4AAICrkNwAAABXMaIqeCTVL8hcXV0d5UgAAECo6n+3Qyms0OqSm/3790uSsrKyohwJAAAI1/79+5WWlha0TaurLeX1evXFF18oJSWlycKdsay6ulpZWVnatWsXtbNsQH/ah760F/1pH/rSXk71p2VZ2r9/vzp16qS4uOCzalrdlZu4uDideeaZ0Q7DcampqfwltRH9aR/60l70p33oS3s50Z8nu2JTjwnFAADAVUhuAACAq5DcuExSUpIef/xxJSUlRTsUV6A/7UNf2ov+tA99aS8T+rPVTSgGAADuxpUbAADgKiQ3AADAVUhuAACAq5DcAAAAVyG5iWF5eXnyeDy6//77m2xTWFgoj8fT6PHpp59GLlBDPfHEE436JSMjI+h7ioqK1L9/fyUnJ+uss87S7NmzIxSt2cLtS87Lk9u9e7duu+02dejQQe3atdN5552nDRs2BH0P52dg4fYl52fTunbtGrBvxo8f3+R7onFetroVit1i3bp1mjNnjvr06RNS+23btjVYKfKMM85wKrSY0rt3b/3973/3P4+Pj2+ybWlpqUaMGKGxY8dq/vz5+uCDD3TvvffqjDPO0E033RSJcI0WTl/W47wMbN++fbrooot02WWX6Z133lF6ero+++wznXbaaU2+h/MzsOb0ZT3Oz8bWrVunuro6//MtW7boyiuv1M033xywfbTOS5KbGHTgwAHdeuutmjt3rp588smQ3pOenh7SX+bWJiEh4aRXa+rNnj1bnTt31syZMyVJPXv21Pr16/XMM8+06h+PeuH0ZT3Oy8BmzJihrKwsvfLKK/5tXbt2Dfoezs/AmtOX9Tg/GzsxwZs+fbq+973v6ZJLLgnYPlrnJcNSMWj8+PG65pprdMUVV4T8nn79+ikzM1NDhw7V+++/72B0sWX79u3q1KmTsrOz9aMf/Uiff/55k21Xr16tYcOGNdh21VVXaf369Tp69KjToRovnL6sx3kZ2OLFizVgwADdfPPNSk9PV79+/TR37tyg7+H8DKw5fVmP8zO42tpazZ8/X3fffXeThaijdV6S3MSYBQsWaOPGjcrLywupfWZmpubMmaOCggItWrRI3bt319ChQ7Vy5UqHIzXf97//fc2bN0/vvvuu5s6dq4qKCg0aNEh79uwJ2L6iokIdO3ZssK1jx446duyYvvrqq0iEbKxw+5LzMrjPP/9c+fn56tatm959912NGzdOEydO1Lx585p8D+dnYM3pS87P0Lz11lv6+uuvdeeddzbZJmrnpYWYsXPnTis9Pd0qLi72b7vkkkus++67L6zPufbaa62RI0faHF3sO3DggNWxY0fr2WefDfh6t27drF//+tcNtv3zn/+0JFnl5eWRCDFmnKwvA+G8PK5NmzZWbm5ug20//elPrYEDBzb5Hs7PwJrTl4FwfjY2bNgw69prrw3aJlrnJVduYsiGDRtUWVmp/v37KyEhQQkJCSoqKtKsWbOUkJDQYJJXMAMHDtT27dsdjjb2nHLKKTr33HOb7JuMjAxVVFQ02FZZWamEhAR16NAhEiHGjJP1ZSCcl8dlZmaqV69eDbb17NlTO3fubPI9nJ+BNacvA+H8bGjHjh36+9//rjFjxgRtF63zkuQmhgwdOlSbN29WcXGx/zFgwADdeuutKi4uDunuFEnatGmTMjMzHY429tTU1Gjr1q1N9k1ubq5WrFjRYNvy5cs1YMAAtWnTJhIhxoyT9WUgnJfHXXTRRdq2bVuDbf/+97/VpUuXJt/D+RlYc/oyEM7Phl555RWlp6frmmuuCdouauelY9eEEBEnDks99NBD1qhRo/zPf/vb31pvvvmm9e9//9vasmWL9dBDD1mSrIKCgihEa5af/exnVmFhofX5559ba9assa699lorJSXFKisrsyyrcV9+/vnnVrt27awHHnjAKikpsV566SWrTZs21sKFC6O1C8YIty85L4Nbu3atlZCQYD311FPW9u3brT/96U9Wu3btrPnz5/vbcH6Gpjl9yfkZXF1dndW5c2dr8uTJjV4z5bwkuYlxJyY3d9xxh3XJJZf4n8+YMcP63ve+ZyUnJ1unn366dfHFF1t/+9vfIh+ogW655RYrMzPTatOmjdWpUyfrxhtvtD755BP/6yf2pWVZVmFhodWvXz8rMTHR6tq1q5Wfnx/hqM0Ubl9yXp7ckiVLrJycHCspKcnq0aOHNWfOnAavc36GLty+5PwM7t1337UkWdu2bWv0minnpceyLMu560IAAACRxZwbAADgKiQ3AADAVUhuAACAq5DcAAAAVyG5AQAArkJyAwAAXIXkBgAAuArJDQAAcBWSGwAx5c4779QNN9zQ5OuvvvqqTjvttIjFczJdu3bVzJkzox0G0KqQ3ACADUxLqoDWjOQGAAC4CskNgJAtXLhQ5557rtq2basOHTroiiuu0MGDB/2vv/LKK+rZs6eSk5PVo0cP/f73v/e/VlZWJo/HowULFmjQoEFKTk5W7969VVhY6G9TV1en0aNHKzs7W23btlX37t31/PPPtzjuJUuWqH///kpOTtZZZ52ladOm6dixY/7XPR6P/vCHP+gHP/iB2rVrp27dumnx4sUNPmPx4sXq1q2b2rZtq8suu0x//OMf5fF49PXXX6uwsFB33XWXqqqq5PF45PF49MQTT/jfe+jQId19991KSUlR586dNWfOnBbvE4AgHC/NCcAVvvjiCyshIcF67rnnrNLSUuvjjz+2XnzxRWv//v2WZVnWnDlzrMzMTKugoMD6/PPPrYKCAqt9+/bWq6++almWZZWWllqSrDPPPNNauHChVVJSYo0ZM8ZKSUmxvvrqK8uyLKu2ttZ67LHHrLVr11qff/65NX/+fKtdu3bWn//8Z38cd9xxh3X99dc3Gecrr7xipaWl+Z8vW7bMSk1NtV599VXrs88+s5YvX2517drVeuKJJ/xt6uN6/fXXre3bt1sTJ060Tj31VGvPnj3+2Nu0aWM9+OCD1qeffmq98cYb1ne/+11LkrVv3z6rpqbGmjlzppWammqVl5db5eXl/n7p0qWL1b59e+vFF1+0tm/fbuXl5VlxcXHW1q1bbTkuABojuQEQkg0bNliSrLKysoCvZ2VlWa+//nqDbb/61a+s3Nxcy7KOJzfTp0/3v3706FHrzDPPtGbMmNHk9957773WTTfd5H8ebnIzePBg69e//nWDNq+99pqVmZnpfy7JeuSRR/zPDxw4YHk8Huudd96xLMuyJk+ebOXk5DT4jIcfftif3AT63npdunSxbrvtNv9zr9drpaenW/n5+U3uA4CWSYjiRSMAMaRv374aOnSozj33XF111VUaNmyY/ud//kenn366vvzyS+3atUujR4/W2LFj/e85duyY0tLSGnxObm6u/88JCQkaMGCAtm7d6t82e/Zs/eEPf9COHTt0+PBh1dbW6rzzzmt23Bs2bNC6dev01FNP+bfV1dXpyJEjOnTokNq1aydJ6tOnj//1U045RSkpKaqsrJQkbdu2TRdccEGDz73wwgtDjuHbn+3xeJSRkeH/bAD2I7kBEJL4+HitWLFCH374oZYvX67f/e53evjhh/XRRx/5E4S5c+fq+9//fqP3nYzH45Ek/eUvf9EDDzygZ599Vrm5uUpJSdFvfvMbffTRR82O2+v1atq0abrxxhsbvZacnOz/c5s2bRrF5PV6JUmWZfljrGdZVsgxBPtsAPYjuQEQMo/Ho4suukgXXXSRHnvsMXXp0kVvvvmmJk2apO9+97v6/PPPdeuttwb9jDVr1mjIkCGSfFd2NmzYoAkTJkiSVq1apUGDBunee+/1t//ss89aFPP555+vbdu26eyzz272Z/To0UNLly5tsG39+vUNnicmJqqurq7Z3wHAPiQ3AELy0Ucf6b333tOwYcOUnp6ujz76SF9++aV69uwpSXriiSc0ceJEpaamavjw4aqpqdH69eu1b98+TZo0yf85L774orp166aePXvqt7/9rfbt26e7775bknT22Wdr3rx5evfdd5Wdna3XXntN69atU3Z2drPjfuyxx3TttdcqKytLN998s+Li4vTxxx9r8+bNevLJJ0P6jJ/85Cd67rnnNHnyZI0ePVrFxcV69dVXJR2/6tS1a1cdOHBA7733nvr27at27dr5r2gBiCxuBQcQktTUVK1cuVIjRozQOeeco0ceeUTPPvushg8fLkkaM2aM/vCHP+jVV1/Vueeeq0suuUSvvvpqo8Rk+vTpmjFjhvr27atVq1bp7bff1ne+8x1J0rhx43TjjTfqlltu0fe//33t2bOnwVWc5rjqqqv017/+VStWrNAFF1yggQMH6rnnnlOXLl1C/ozs7GwtXLhQixYtUp8+fZSfn6+HH35YkpSUlCRJGjRokMaNG6dbbrlFZ5xxhp5++ukWxQ2g+TxWOAPHANBMZWVlys7O1qZNm1o0QdgUTz31lGbPnq1du3ZFOxQAJ2BYCgBC8Pvf/14XXHCBOnTooA8++EC/+c1v/HOFAJiF5AYAQrB9+3Y9+eST2rt3rzp37qyf/exnmjJlSrTDAhAAw1IAAMBVmFAMAABcheQGAAC4CskNAABwFZIbAADgKiQ3AADAVUhuAACAq5DcAAAAVyG5AQAArvL/AWHvEPxj7KtnAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')\n",
    "plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')\n",
    "plt.xlabel('sepal length')\n",
    "plt.ylabel('sepal width')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array(df.iloc[:100, [0, 1, -1]])\n",
    "X, y = data[:,:-1], data[:,-1]\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KNN:\n",
    "    def __init__(self, X_train, y_train, n_neighbors=3, p=2):\n",
    "        \"\"\"\n",
    "        parameter: n_neighbors 临近点个数\n",
    "        parameter: p 距离度量\n",
    "        \"\"\"\n",
    "        self.n = n_neighbors\n",
    "        self.p = p\n",
    "        self.X_train = X_train\n",
    "        self.y_train = y_train\n",
    "\n",
    "    def predict(self, X):\n",
    "        # 取出n个点\n",
    "        knn_list = []\n",
    "        for i in range(self.n):\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            knn_list.append((dist, self.y_train[i]))\n",
    "\n",
    "        for i in range(self.n, len(self.X_train)):\n",
    "            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))\n",
    "            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)\n",
    "            if knn_list[max_index][0] > dist:\n",
    "                knn_list[max_index] = (dist, self.y_train[i])\n",
    "\n",
    "        # 统计\n",
    "        knn = [k[-1] for k in knn_list]\n",
    "        count_pairs = Counter(knn)\n",
    "#         max_count = sorted(count_pairs, key=lambda x: x)[-1]\n",
    "        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]\n",
    "        return max_count\n",
    "\n",
    "    def score(self, X_test, y_test):\n",
    "        right_count = 0\n",
    "        n = 10\n",
    "        for X, y in zip(X_test, y_test):\n",
    "            label = self.predict(X)\n",
    "            if label == y:\n",
    "                right_count += 1\n",
    "        return right_count / len(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = KNN(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Point: 1.0\n"
     ]
    }
   ],
   "source": [
    "test_point = [6.0, 3.0]\n",
    "print('Test Point: {}'.format(clf.predict(test_point)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x226dccab9d0>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjcAAAGzCAYAAADT4Tb9AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy88F64QAAAACXBIWXMAAA9hAAAPYQGoP6dpAABHzklEQVR4nO3de1xUZf4H8M8AckvAIJFBEaa8IOIdXcG8ZaFSVmtb7VaWeXktqWmylqmluWlom4VuhgtblrHl7kssdde81Aaal7xSKmT+FNTVIfIGXkFmzu+PkdGRmWEGzpl55szn/Xrxyjk8c+Z7nnNyvp7nOc9XI0mSBCIiIiKV8HF3AERERERyYnJDREREqsLkhoiIiFSFyQ0RERGpCpMbIiIiUhUmN0RERKQqTG6IiIhIVZjcEBERkaowuSEiIiJVYXJDREREquLn7gDqZGZmYubMmZgyZQqysrKstikoKMDgwYPrbS8pKUF8fLxDn2M0GnH69GmEhIRAo9E0JWQiIiJyEUmScPHiRURHR8PHx/69GSGSm927dyMnJwddu3Z1qP3hw4cRGhpqft2yZUuHP+v06dOIiYlxOkYiIiJyv5MnT6JNmzZ227g9ubl06RKefvpp5ObmYt68eQ69JzIyEi1atGjU54WEhAAwdc6tCRIRERGJq6qqCjExMebvcXvcntxMnDgRDz74IO6//36Hk5sePXrg2rVrSEhIwGuvvWZ1qKpOdXU1qqurza8vXrwIAAgNDWVyQ0RE5GEcmVLi1uRm5cqV2LdvH3bv3u1Qe61Wi5ycHPTq1QvV1dX49NNPMWTIEBQUFGDAgAFW35OZmYm5c+fKGTYREREJTCNJkuSODz558iSSkpKwadMmdOvWDQAwaNAgdO/e3eaEYmtGjBgBjUaDtWvXWv397Xdu6m5rVVZW8s4NERGRh6iqqkJYWJhD399uexR87969qKioQK9eveDn5wc/Pz8UFhZiyZIl8PPzg8FgcGg/ffv2xZEjR2z+PiAgwDwExaEoIiIi9XPbsNSQIUNw4MABi23PP/884uPjMX36dPj6+jq0n/3790Or1SoRIhERCc5gMOD69evuDoNk4u/v3+Bj3o5wW3ITEhKCxMREi2133HEHIiIizNtnzJiBU6dOYcWKFQCArKwsxMXFoXPnzqipqUFeXh7y8/ORn5/v8viJiMh9JElCeXk5Lly44O5QSEY+Pj7Q6XTw9/dv0n7c/rSUPXq9HidOnDC/rqmpwbRp03Dq1CkEBQWhc+fO+M9//oO0tDQ3RklERK5Wl9hERkYiODiYi7KqQN0iu3q9Hm3btm3SOXXbhGJ3cWZCEhERicdgMODnn39GZGQkIiIi3B0OyaiyshKnT59Gu3bt0KxZM4vfecSEYiIiosaom2MTHBzs5khIbnXDUY4+VGQLkxsiIvJIHIpSH7nOqdBzboiI5GQwSthVeg4VF68hMiQQfXTh8PXhFySR2jC5ISKvsOGgHnPXFUNfec28TRsWiDkjEjAskctJEKkJh6WISPU2HNTjhbx9FokNAJRXXsMLefuw4aDeTZGRt/rggw+g0+kQGBiIXr16YevWre4OSVWY3BCRqhmMEuauK4a1x0Lrts1dVwyD0aseHKUbDEYJO46exZqiU9hx9KxLroN//vOfeOmllzBr1izs378f/fv3x/Dhwy2WPqGm4bAUEanartJz9e7Y3EoCoK+8hl2l55B8Dx8r9ibuGqp89913MXbsWIwbNw6AaYHajRs3Ijs7G5mZmYp9rjfhnRsiUrWKi7YTm8a0I3Vw11BlTU0N9u7di9TUVIvtqamp2L59uyKf6Y2Y3BCRqkWGBMrajjyfO4cqz5w5A4PBgFatWllsb9WqFcrLy2X/PG/F5IaIVK2PLhzasEDYeuBbA9NQRB9duCvDIjdyZqhSKbev5yJJEtftkRGTGyJSNV8fDeaMSACAeglO3es5IxK43o0XcedQ5V133QVfX996d2kqKirq3c2hxmNyQ0SqNyxRi+xneiIqzHLoKSosENnP9OQ6N17GnUOV/v7+6NWrFzZv3myxffPmzUhJSZH987wVn5YiIq8wLFGLBxKiuEIxmYcqyyuvWZ13o4Ep8VVqqDIjIwOjRo1CUlISkpOTkZOTgxMnTiA9PV2Rz/NGTG6IyGv4+mj4uDeZhypfyNsHDWCR4LhiqPLJJ5/E2bNn8ec//xl6vR6JiYlYv349YmNjFfk8b8RhKSIi8jruHqqcMGECysrKUF1djb1792LAgAGKfp634Z0bIiLyShyqVC8mN0RE5LU4VKlOHJYiIiIiVWFyQ0RERKrC5IaIiIhUhckNERERqQqTGyIiIlIVJjdERESkKkxuiIiISFWY3BAREZGqMLkhIiJykS1btmDEiBGIjo6GRqPBl19+6e6QVInJDREReS+jASjdChxYZfqv0aDox12+fBndunXD+++/r+jneDuWXyAiIu9UvBbYMB2oOn1zW2g0MGwhkPCwIh85fPhwDB8+XJF90028c0NERN6neC3wr2ctExsAqNKbthevdU9cJAsmN0RE5F2MBtMdG0hWfnlj24ZXFR+iIuUwuSEixRmMEnYcPYs1Raew4+hZGIzWvlSIXOT49vp3bCxIQNUpUzvySJxzQ0SK2nBQj7nriqGvvGbepg0LxJwRCRiWqHVjZOS1Lv0ibzsSDu/cEJFiNhzU44W8fRaJDQCUV17DC3n7sOGg3k2RkVdr3krediQcJjdEpAiDUcLcdcX2ZjVg7rpiDlGR68WmmJ6KgsZGAw0Q2trUTmaXLl1CUVERioqKAAClpaUoKirCiRMnZP8sb8bkhogUsav0XL07NreSAOgrr2FX6TnXBUUEAD6+pse9AdRPcG68HrbA1E5me/bsQY8ePdCjRw8AQEZGBnr06IHZs2fL/lnejHNuiEgRFRdtJzaNaUckq4SHgSdW2FjnZoFi69wMGjQIksS7lUpjckNEiogMCZS1HZHsEh4G4h80PRV16RfTHJvYFEXu2JBrMbkhIkX00YVDGxaI8sprVufdaABEhQWijy7c1aER3eTjC+j6uzsKkhnn3BCRInx9NJgzIgGAzVkNmDMiAb4+tiZ1EhE1DpMbIlLMsEQtsp/piagwy6GnqLBAZD/Tk+vcEJEiOCxFRIoalqjFAwlR2FV6DhUXryEyxDQUxTs2RKQUJjdEpDhfHw2S74lwdxhE5CU4LEVERESqwuSGiIiIVIXDUkQCMxglzlUhInISkxsiQbGaNhGJatCgQejevTuysrLcHYpVHJYiEhCraRO5hsEAFBQAn39u+q/BoOznDRo0CC+99JJs+xs9ejQeffRR2fbnqNWrV+PNN990uH1ZWRk0Go25YKjSmNwQCYbVtIlcY/VqIC4OGDwYeOop03/j4kzbyb7w8HCEhIS4OwybmNwQCYbVtImUt3o18LvfAf/7n+X2U6dM25VIcEaPHo3CwkIsXrwYGo0GGo0GZWVlKC4uRlpaGpo3b45WrVph1KhROHPmjPl9q1atQpcuXRAUFISIiAjcf//9uHz5Mt544w188sknWLNmjXl/BQUFdmOou4OycuVKpKSkIDAwEJ07d673vsLCQvTp0wcBAQHQarV49dVXUVtba/797Xeg4uLi8NZbb2HMmDEICQlB27ZtkZOTY/69TqcDAPTo0QMajQaDBg1qdD86gskNkWBYTZtIWQYDMGUKYK04d922l16Sf4hq8eLFSE5Oxvjx46HX66HX69GsWTMMHDgQ3bt3x549e7Bhwwb88ssveOKJJwAAer0ef/jDHzBmzBiUlJSgoKAAI0eOhCRJmDZtGp544gkMGzbMvL+UlBSHYnn55Zfxpz/9Cfv370dKSgoefvhhnD17FgBw6tQppKWloXfv3vjhhx+QnZ2NDz/8EPPmzbO7z0WLFiEpKQn79+/HhAkT8MILL+Cnn34CAOzatQsA8PXXX0Ov12O1wrfHOKGYSDCspk2krK1b69+xuZUkASdPmtrJeYMhLCwM/v7+CA4ORlRUFABg9uzZ6NmzJ9566y1zu48++ggxMTH4+eefcenSJdTW1mLkyJGIjY0FAHTp0sXcNigoCNXV1eb9OWrSpEl47LHHAADZ2dnYsGEDPvzwQ7zyyiv44IMPEBMTg/fffx8ajQbx8fE4ffo0pk+fjtmzZ8PHx/p9kbS0NEyYMAEAMH36dLz33nsoKChAfHw8WrZsCQCIiIhwOtbG4J0bIsHUVdO29cC3BqanplhNm6hx9A7Ox3e0XVPs3bsX3377LZo3b27+iY+PBwAcPXoU3bp1w5AhQ9ClSxc8/vjjyM3Nxfnz55v8ucnJyeY/+/n5ISkpCSUlJQCAkpISJCcnQ6O5+bdQv379cOnSJfzPTlbYtWtX8581Gg2ioqJQUVHR5Fgbg8kNkWBYTZtIWVoHV1JwtF1TGI1GjBgxAkVFRRY/R44cwYABA+Dr64vNmzfjq6++QkJCAv7617+iY8eOKC0tlT2WumRGkiSLxKZu261trGnWrFm9/RmNRpmjdAyTGyIBsZo2kXL69wfatAFsfU9rNEBMjKmd3Pz9/WG4ZTJPz549cejQIcTFxaFdu3YWP3fccceNeDTo168f5s6di/3798Pf3x9ffPGF1f05aufOneY/19bWYu/eveY7RgkJCdi+fbs5oQGA7du3IyQkBK1bt270cQNoVKyNwTk3RIJiNW0iZfj6AosXm56K0mgsJxbXJTxZWaZ2couLi8P333+PsrIyNG/eHBMnTkRubi7+8Ic/4OWXX8Zdd92F//u//8PKlSuRm5uLPXv24JtvvkFqaioiIyPx/fff49dff0WnTp3M+9u4cSMOHz6MiIgIhIWF1buDYs3SpUvRvn17dOrUCe+99x7Onz+PMWPGAAAmTJiArKwsvPjii5g0aRIOHz6MOXPmICMjw+Z8m4ZERkYiKCgIGzZsQJs2bRAYGIiwsLBG7csRvHNDJLC6atqPdG+N5HsimNgQyWTkSGDVKuD2GxFt2pi2jxypzOdOmzYNvr6+SEhIQMuWLVFTU4Nt27bBYDBg6NChSExMxJQpUxAWFgYfHx+EhoZiy5YtSEtLQ4cOHfDaa69h0aJFGD58OABg/Pjx6NixI5KSktCyZUts27bNoTgWLFiAhQsXolu3bti6dSvWrFmDu+66CwDQunVrrF+/Hrt27UK3bt2Qnp6OsWPH4rXXXmv0cfv5+WHJkiX429/+hujoaDzyyCON3pcjNJJk7WE49aqqqkJYWBgqKysRGhrq7nCIiMhJ165dQ2lpKXQ6HQIDm/bUoMFgeipKrzfNsenfX5k7NqIoKyuDTqfD/v370b17d3eHU4+9c+vM9zeHpYiIyGv5+sr7uDeJgcNSREQOMhgl7Dh6FmuKTmHH0bMsgUHCeeuttyweK7/1p24oyxsIc+cmMzMTM2fOxJQpU+xWGS0sLERGRgYOHTqE6OhovPLKK0hPT3ddoETklVilnTxBenq6eXXj2wUFBaF169bwhtkoQiQ3u3fvRk5OjsUCQNaUlpYiLS0N48ePR15eHrZt24YJEyagZcuW5pUWiYjkVlel/favhLoq7Xw8n0QRHh6O8HAu8On2YalLly7h6aefRm5uLu688067bZctW4a2bdsiKysLnTp1wrhx4zBmzBi88847LoqWiLwNq7SLyxvuQHgbuc6p25ObiRMn4sEHH8T999/fYNsdO3YgNTXVYtvQoUOxZ88eXL9+3ep7qqurUVVVZfFDROQoVmkXT906LleuXHFzJCS3mpoaAIBvEx9Zc+uw1MqVK7Fv3z7s3r3bofbl5eVo1aqVxbZWrVqhtrYWZ86cgdbKWtmZmZmYO3euLPESkfdhlXbx+Pr6okWLFua6RcHBwXbLApBnMBqN+PXXXxEcHAw/v6alJ25Lbk6ePIkpU6Zg06ZNTq1T4Gy9ixkzZiAjI8P8uqqqCjExMY2ImIi8Eau0i6musrS7CjOSMnx8fNC2bdsmJ6tuS2727t2LiooK9OrVy7zNYDBgy5YteP/991FdXV3vtlRUVBTKy8sttlVUVMDPzw8RERFWPycgIAABAQHyHwAReYW6Ku3lldeszrvRwFTzi1XaXUuj0UCr1SIyMtLmtATyPP7+/o0u8XArtyU3Q4YMwYEDByy2Pf/884iPj8f06dOtjrclJydj3bp1Fts2bdqEpKQkh2ppEBE5q65K+wt5+6ABLBIcVml3P19f3ybPzyD1cduE4pCQECQmJlr83HHHHYiIiEBiYiIA05DSs88+a35Peno6jh8/joyMDJSUlOCjjz7Chx9+iGnTprnrMIjIC7BKO5FnEWKdG1v0ej1OnDhhfq3T6bB+/XpMnToVS5cuRXR0NJYsWcI1bohIcazSTuQ5WDiTiIiIhOfM97fb17khIiIikhOTGyIiIlIVoefcEJEYamqN+HRHGY6fu4LY8GCMSo6Dvx//bUREYmJyQ0R2Za4vRu7WUtxaOmn++hKM76/DjLQE9wVGRGQDkxsisilzfTH+tqW03najBPN2JjhEJBreVyYiq2pqjcjdWj+xuVXu1lLU1BpdFBERkWOY3BCRVZ/uKLMYirLGKJnaERGJhMkNEVl1/NwVWdsREbkKkxsisio2PFjWdkRErsLkhoisGpUch4YqC/hoTO2IiETC5IaIrPL388H4/jq7bcb313G9GyISDh8FJyKb6h7zvn2dGx8NuM4NEQmLhTOJqEFcoZiI3M2Z72/euSGiBvn7+WBs/7vdHQYRkUP4Ty8iIiJSFSY3REREpCocliJS0NUaA95aX4yys1cQFxGMmWkJCPL3dXdYXstglLCr9BwqLl5DZEgg+ujC4dvQ8+5E5HGY3BApZPyK3dhcXGF+vfUI8OnOE3ggIRK5z/Z2Y2TeacNBPeauK4a+8pp5mzYsEHNGJGBYotaNkRGR3DgsRaSA2xObW20ursD4FbtdHJF323BQjxfy9lkkNgBQXnkNL+Ttw4aDejdFRkRKYHJDJLOrNQabiU2dzcUVuFpjcFFE3s1glDB3XTGsrXlRt23uumIYGqoSSkQeg8kNkczeWl8saztqml2l5+rdsbmVBEBfeQ27Ss+5LigiUhSTGyKZlZ11rEq2o+2oaSou2k5sGtOOiMTH5IZIZnERjlXJdrQdNU1kSKCs7YhIfExuiGQ208F6S462o6bpowuHNiwQth741sD01FQfXbgrwyIiBTG5IZJZkL8vHkiItNvmgYRIrnfjIr4+GswZYUokb09w6l7PGZHA9W6IVITJDZECcp/tbTPB4To3rjcsUYvsZ3oiKsxy6CkqLBDZz/TkOjdEKsOq4EQK4grFYuEKxUSey5nvbyY3REREJDxnvr85LEVERESqwuSGiIiIVIWFM4kUJMIcDzliEOE4iIgcxeSGSCEiVKGWIwYRjoOIyBkcliJSgAhVqOWIQYTjICJyFpMbIpmJUIVajhhEOA4iosZgckMkMxGqUMsRgwjHQUTUGExuiGQmQhVqOWIQ4TiIiBqDyQ2RzESoQi1HDCIcBxFRYzC5IZKZCFWo5YhBhOMgImoMJjdEMhOhCrUcMYhwHEREjcHkhkgBIlShliMGEY6DiMhZLJxJpCARVvblCsVEpAbOfH9zhWIiBfn6aJB8T4THxyDCcRAROYrDUkRERKQqTG6IiIhIVTgsRRbUMreC80yIiLwXkxsyU0v1Z1bCJiLybhyWIgDqqf7MSthERMTkhlRT/ZmVsImICGByQ1BP9WdWwiYiIoDJDUE91Z9ZCZuIiAAmNwT1VH9mJWwiIgKY3BDUU/2ZlbCJiAhgckNQT/VnVsImIiKAyQ3doJbqz6yETURErApOFtSyKi9XKCYiUhdWBadGU0v1Z1bCJiLyXhyWIiIiIlVhckNERESqwmEpIhtqao34dEcZjp+7gtjwYIxKjoO/n3P/HmjqPtQy70ctx0FEnsGtE4qzs7ORnZ2NsrIyAEDnzp0xe/ZsDB8+3Gr7goICDB48uN72kpISxMfHO/SZnFBMjshcX4zcraW4tYSUjwYY31+HGWkJLtmHWiqTq+U4iMi9nPn+duuwVJs2bbBgwQLs2bMHe/bswX333YdHHnkEhw4dsvu+w4cPQ6/Xm3/at2/voojJG2SuL8bftlgmJQBglIC/bSlF5vpixfehlsrkajkOIvIsbk1uRowYgbS0NHTo0AEdOnTA/Pnz0bx5c+zcudPu+yIjIxEVFWX+8fX1dVHEpHY1tUbkbi212yZ3aylqao2K7UMtlcnVchxE5HmEmVBsMBiwcuVKXL58GcnJyXbb9ujRA1qtFkOGDMG3335rt211dTWqqqosfohs+XRHWb27LbczSqZ2Su1DLZXJ1XIcROR53J7cHDhwAM2bN0dAQADS09PxxRdfICHB+nwErVaLnJwc5OfnY/Xq1ejYsSOGDBmCLVu22Nx/ZmYmwsLCzD8xMTFKHQqpwPFzV5rcrqn7UEtlcrUcBxF5Hrc/LdWxY0cUFRXhwoULyM/Px3PPPYfCwkKrCU7Hjh3RsWNH8+vk5GScPHkS77zzDgYMGGB1/zNmzEBGRob5dVVVFRMcsik2PLjJ7Zq6D7VUJlfLcRCR53H7nRt/f3+0a9cOSUlJyMzMRLdu3bB48WKH39+3b18cOXLE5u8DAgIQGhpq8UNky6jkODT0hLKPxtROqX2opTK5Wo6DiDyP25Ob20mShOrqaofb79+/H1otHyclefj7+WB8f53dNuP76+yuVdPUfailMrlajoOIPE+jhqW++eYbfPPNN6ioqIDRaPnEx0cffeTwfmbOnInhw4cjJiYGFy9exMqVK1FQUIANGzYAMA0pnTp1CitWrAAAZGVlIS4uDp07d0ZNTQ3y8vKQn5+P/Pz8xhwGkVV1a9A0ZY2apu6jrjL57evDRHnY+jBqOQ4i8ixOJzdz587Fn//8ZyQlJUGr1UKjafy/un755ReMGjUKer0eYWFh6Nq1KzZs2IAHHngAAKDX63HixAlz+5qaGkybNg2nTp1CUFAQOnfujP/85z9IS0trdAxE1sxIS8CfUuObtLpwU/cxLFGLBxKiPH5lX7UcBxF5DqdXKNZqtXj77bcxatQopWJSFFcoJiIi8jyKrlBcU1ODlJSURgdHREREpCSnk5tx48bhs88+UyIWIiIioiZzaM7NrevEGI1G5OTk4Ouvv0bXrl3RrFkzi7bvvvuuvBGSS4lQvVmOatyixNHU/hThfADinBO6wWgAjm8HLv0CNG8FxKYAPixDQ1THoTk31ipx29JQOQR345wb20So3ixHNW5R4mhqf4pwPgBxzgndULwW2DAdqDp9c1toNDBsIZDwsPviIlKYM9/fTk8o9nRMbqyrq958+8VQd48g+5mein+h1lXStuWPA1zzZSpHHE3tTxHOByDOOaEbitcC/3oWsHVlPLGCCQ6plqITiseMGYOLFy/W23758mWMGTPG2d2RAESo3ixHNW5R4mhqf4pwPgBxzgndYDSY7tjYuzI2vGpqR+TlnE5uPvnkE1y9erXe9qtXr5oX2yPPIkL1ZjmqcYsSR1P7U4TzAYhzTuiG49sth6LqkYCqU6Z2RF7O4UX8qqqqIEkSJEnCxYsXERh4s9idwWDA+vXrERkZqUiQpCwRqjfLUY1blDia2p8inA9AnHNCN1z6Rd52RCrmcHLTokULaDQaaDQadOjQod7vNRoN5s6dK2tw5BoiVG+Woxq3KHE0tT9FOB+AOOeEbmjeSt52RCrmcHLz7bffQpIk3HfffcjPz0d4+M1Kvv7+/oiNjUV0dLQiQZKy6qo3l1deszqar4GpFpCS1ZtHJcdh/voSu8MgDVXjFiWOpvanCOcDEOec0A2xKaanoqr0sD7vRmP6fSwXWSVyeM7NwIEDMWjQIJSWluLRRx/FwIEDzT/JyclMbDyYCNWb5ajGLUocTe1PEc4HIM45oRt8fE2PewOweWUMW8D1bojg4KPgP/74o8M77Nq1a5MCUhofBbdNhHVVRFlThevc3CTKOaEbrK5z09qU2PAxcFIx2de58fHxgUajgSRJDVYBNxjEfgyRyY19IqyIK8pquFyh+CZRzgndwBWKyQvJntwcP37c/Of9+/dj2rRpePnll5GcnAwA2LFjBxYtWoS3334bjz76aNOiVxiTGyIiIs/jzPe3QxOKY2NjzX9+/PHHsWTJEqSlpZm3de3aFTExMXj99deFT26IiIhI3Zy+r3zgwAHodPUnGep0OhQXF8sSFBEREVFjOZ3cdOrUCfPmzcO1azcnOVZXV2PevHno1KmTrMERuZPBKGHH0bNYU3QKO46ebVS5Azn2QaRaRgNQuhU4sMr0X5aOIJk4vM5NnWXLlmHEiBGIiYlBt27dAAA//PADNBoN/v3vf8seIJE7yPGkkihPOxEJidXNSUGNqgp+5coV5OXl4aeffoIkSUhISMBTTz2FO+64Q4kYZcUJxdQQOSpyi1LVm0hIrG5OjSD701JqwuSG7DEYJdy78L82C1fWrQ783fT7bD6SLcc+iFTLaACyEu0UAb2x0vJLB/h4O1mQ/WmptWvXYvjw4WjWrBnWrl1rt+3DDzPbJs/lTEXu5HsiFNsHkWo5U91c199lYZG6OJTcPProoygvL0dkZKTdR701Go3wi/gR2SNHRW5RqnoTCYnVzckFHEpujEaj1T8TqY0cFblFqepNJCRWNycXcPpR8CtXrigRB5EQ6ipy25oJo4HpiSd7Fbnl2AeRatVVN7f3f0hoa1Y3pyZxOrlp0aIFUlJSMHPmTGzcuBGXL19WIi4it5CjIrcoVb2JhMTq5uQCTic3hYWFePjhh7Fv3z48/vjjuPPOO9G3b1+8+uqr+Oqrr5SIkcilhiVqkf1MT0SFWQ4bRYUFOvwItxz7IFKthIdNj3uH3vb/QWg0HwMnWTTpUXCDwYDdu3dj2bJl+Mc//gGj0Sj8hGI+Ck6OkqMityhVvYmExOrm5ATZHwW/3U8//YSCggIUFhaioKAA169fx4gRIzBw4MBGBUwkIl8fTZMf1ZZjH0Sq5ePLx71JEU4nN1FRUbh+/Truu+8+DBo0CDNnzkSXLl2UiI2IiIjIaU7PuYmKisKlS5dw4sQJnDhxAv/73/9w6dIlJWIjIiIicprTd26Kiopw4cIFbNmyBYWFhXj99ddx6NAhdO3aFYMHD8aCBQuUiNMriDA/Q44YamqN+HRHGY6fu4LY8GCMSo6Dv5/TebTbiXA+SIU4z0Re7E+xCHI+mjSh+Ny5cygoKMCaNWvw2WefcUJxE4hQQVqOGDLXFyN3aymMt1xVPhpgfH8dZqQlyB2yYkQ4H6RCrIQtL/anWBQ+H4oWzvziiy9QUFCAgoICHDp0CBEREejfvz8GDRqEwYMHo3Pnzk0KXmkiJjciVJCWI4bM9cX425ZSm7//4wDPSHBEOB+kQqyELS/2p1hccD4UTW4iIyMxYMAADBo0CIMGDUJiYmKTgnU10ZIbESpIyxFDTa0R8a9/ZXHH5nY+GuCnN4cLPUQlwvkgFWIlbHmxP8XiovPhzPe3098yFRUVWLVqFSZNmuRxiY2InKkgLXIMn+4os5vYAIBRMrUTmQjng1TImUrY1DD2p1gEPB/i/hPaS4hQQVqOGI6fc6zmmKPt3EWE80EqxErY8mJ/ikXA88Hkxs1EqCAtRwyx4cEO7cPRdu4iwvkgFWIlbHmxP8Ui4PlgcuNmIlSQliOGUclxaGgKio/G1E5kIpwPUiFWwpYX+1MsAp4PJjduJkIFaTli8Pfzwfj+OrufM76/TujJxIAY54NUiJWw5cX+FIuA50PsbxovIUIFaTlimJGWgD8O0NW7g+Oj8ZzHwAExzgepECthy4v9KRbBzodDj4KPHDnS4R2uXr26SQEpTbRHwW8lwoq4XKH4JhHOB6mQICu4qgb7UywKng/Zq4KHhYXJEhjZJ0IFaTli8Pfzwdj+d8sUkfuIcD5IhVgJW17sT7EIcj4cSm6WL1+udBxEREREsvC8sQIiIiIiO5yuCg4Aq1atwr/+9S+cOHECNTU1Fr/bt2+fLIGRe4gwz4TzfojI69TWALtzgfNlwJ1xQO/xgJ+/a2NQ0fwlp5ObJUuWYNasWXjuueewZs0aPP/88zh69Ch2796NiRMnKhEjuYgIlbCVqkw+f32Jx1UmJyIvsel1YMf7gGS8ZdtrQPIkIPVN18SgsgrrThfOjI+Px5w5c/CHP/wBISEh+OGHH3D33Xdj9uzZOHfuHN5//32lYpWFyE9LuZMIlbBZmZyIvM6m14HtS2z/PmWy8gmOh1RYV7Rw5okTJ5CSYlplMCgoCBcvXgQAjBo1Cp9//nkjwiV3MxglzF1XXO+yBm5e6nPXFcPQUGVMN8dQU2tE7lbbiQ0A5G4tRU2t0W4bIiKXqK0x3bGxZ8dSUzulGA2mOzb2/vbd8KqpnQdxOrmJiorC2bNnAQCxsbHYuXMnAKC0tBRO3gQiQYhQCZuVyYnI6+zOtRyKskYymNopRcCK3nJwOrm57777sG7dOgDA2LFjMXXqVDzwwAN48skn8dvf/lb2AEl5IlTCZmVyIvI658vkbdcYAlb0loPTE4pzcnJgNJoyzfT0dISHh+O7777DiBEjkJ6eLnuApDwRKmGzMjkReZ074+Rt1xgCVvSWg9N3bnx8fODndzMneuKJJ7BkyRJMnjwZ/v4ufmyNZCFCJWxWJicir9N7PKBp4GtY42tqpxQBK3rLoVELf5w/fx7vvPMOxo4di3HjxmHRokU4d065+RikLBEqYbMyORF5HT9/0+Pe9iRPVHa9GwEresvB6b/lCwsLodPpsGTJEpw/fx7nzp3DkiVLoNPpUFhYqESM5AIiVMJmZXIi8jqpb5oe9779Do7G1zWPgQPCVfSWg9Pr3CQmJiIlJQXZ2dnw9TVlcgaDARMmTMC2bdtw8OBBRQKVC9e5sY8rFBMRuQFXKG6QM9/fTic3QUFBKCoqQseOHS22Hz58GN27d8fVq1edj9iFmNwQERF5HkUX8evZsydKSkrqbS8pKUH37t2d3R0RERGRrJx+FHzy5MmYMmUK/u///g99+/YFAOzcuRNLly7FggUL8OOPP5rbdu3aVb5IiYiIiBzg9LCUj4/9mz0ajQaSJEGj0cBgEG+5ZqWGpeSYJyLCfBcRyDFfhudDZiKMxcsxJ0GE45AhBoMB2LoV0OsBrRbo3x/wdfYwROgLtZCjL3k+GuTM97fTd25KS+3X7nFGdnY2srOzUVZWBgDo3LkzZs+ejeHDh9t8T2FhITIyMnDo0CFER0fjlVdecfvigXJUshahIrcI5KjozfMhMxGqBctRNVmE45AhhtWrgSlTgP/97+a2Nm2AxYuBkSNdFwfdIEdf8nzIzuk7N3Jat24dfH190a5dOwDAJ598gr/85S/Yv38/OnfuXK99aWkpEhMTMX78ePzxj3/Etm3bMGHCBHz++ed47LHHHPpMue/cyFHJWoSK3CKQo6I3z4fMRKgWLEfVZBGOQ4YYVq8Gfvc74Pa/tTU3drFqlQMJjgh9oRZy9CXPh8MUnVAMAJ9++in69euH6OhoHD9+HACQlZWFNWvWOLWfESNGIC0tDR06dECHDh0wf/58NG/e3FyM83bLli1D27ZtkZWVhU6dOmHcuHEYM2YM3nnnncYcRpPJUclahIrcIpCjojfPh8xEqBYsR9VkEY5DhhgMBtMdG2v/HK3b9tJLpnZKxkE3yNGXPB+KcTq5yc7ORkZGBtLS0nDhwgXzvJoWLVogKyur0YEYDAasXLkSly9fRnJystU2O3bsQGpqqsW2oUOHYs+ePbh+/brV91RXV6OqqsriRy5yVLIWoSK3COSo6M3zITMRqgXLUTVZhOOQIYatWy2HourtQQJOnjS1UzIOukGOvuT5UIzTyc1f//pX5ObmYtasWeZF/AAgKSkJBw4ccDqAAwcOoHnz5ggICEB6ejq++OILJCRYH3ooLy9Hq1aWxbtatWqF2tpanDlzxup7MjMzERYWZv6JiYlxOkZb5KhkLUJFbhHIUdGb50NmIlQLlqNqsgjHIUMMer1ju7DbToS+UAs5+pLnQzFOJzelpaXo0aNHve0BAQG4fPmy0wF07NgRRUVF2LlzJ1544QU899xzKC4uttleo7F8WqVuytDt2+vMmDEDlZWV5p+TJ086HaMtclSyFqEitwjkqOjN8yEzEaoFy1E1WYTjkCEGrYPTvOy2E6Ev1EKOvuT5UIzTyY1Op0NRUVG97V999ZXNOy72+Pv7o127dkhKSkJmZia6deuGxYsXW20bFRWF8vJyi20VFRXw8/NDRESE1fcEBAQgNDTU4kcuclSyFqEitwjkqOjN8yEzEaoFy1E1WYTjkCGG/v1NT0XZ+HccNBogJsbUTsk46AY5+pLnQzFOJzcvv/wyJk6ciH/+85+QJAm7du3C/PnzMXPmTLz88stNDkiSJFRXV1v9XXJyMjZv3myxbdOmTUhKSkKzZs2a/NnOkqOStQgVuUUgR0Vvng+ZiVAtWI6qySIchwwx+PqaHvcG6ic4da+zshpY70aEvlALOfqS50MxTic3zz//PObMmYNXXnkFV65cwVNPPYVly5Zh8eLF+P3vf+/UvmbOnImtW7eirKwMBw4cwKxZs1BQUICnn34agGlI6dlnnzW3T09Px/Hjx5GRkYGSkhJ89NFH+PDDDzFt2jRnD0M2clSyFqEitwjkqOjN8yEzEaoFy1E1WYTjkCGGkSNNj3u3bm25vU0bBx8DlykOukGOvuT5UEST1rk5c+YMjEYjIiMjG/X+sWPH4ptvvoFer0dYWBi6du2K6dOn44EHHgAAjB49GmVlZSgoKDC/p7CwEFOnTjUv4jd9+nSnFvHjCsXi4wrFAhJh9VSuUGzGFYoFwxWKXULRquBXr16FJEkIDjZN7Dx+/Lj5CafbH9MWEauCExEReR5FF/F75JFHsGLFCgDAhQsX0KdPHyxatAiPPPIIsrOzGxcxERERkUycTm727duH/jem469atQpRUVE4fvw4VqxYgSVL7CyRTkREROQCThfOvHLlCkJCQgCYnlQaOXIkfHx80LdvX3MpBmoczvEgsoPzGm4SoS9E6UsR4hAhBrLgdHLTrl07fPnll/jtb3+LjRs3YurUqQBM681wDkvjsQo1kR2svHyTCH0hSl+KEIcIMVA9Tk8oXrVqFZ566ikYDAYMGTIEmzZtAmAqc7BlyxZ89dVXigQqFxEnFLMKNZEdrLx8kwh9IUpfihCHCDF4EUWflgJMNZ70ej26desGHx/TtJ1du3YhNDQU8fHxjYvaRURLbgxGCfcu/K/NYo0amNZX+W76fRyiIu9jNABZiXaKC2pM/0p+6YDtYQA59iECEfpClL4UIQ4RYvAyij4tBZjKIPTo0cOc2ABAnz59hE9sRMQq1ER2sPLyTSL0hSh9KUIcIsRANjUquSH5sAo1kR2svHyTCH0hSl+KEIcIMZBNTG7cjFWoiexg5eWbROgLUfpShDhEiIFsYnLjZqxCTWQHKy/fJEJfiNKXIsQhQgxkE5MbN2MVaiI7WHn5JhH6QpS+FCEOEWIgm5jcCIBVqInsYOXlm0ToC1H6UoQ4RIiBrGpSVXBPJNqj4LfiCsVEdoiwKq8oROgLUfpShDhEiMELKL7OjScTObkhIiIi6xRf54aIiIhIVExuiIiISFWcLpxJROSxamuA3bnA+TLgzjig93jAz9/dUbkH+8JELfNl1HIcMuGcGyLyDpteB3a8D0jGm9s0PkDyJCD1TffF5Q7sCxO1VPRWy3E0gHNuiIhutel1YPsSyy9zwPR6+xLT770F+8KkrqL37fWhqvSm7cVr3ROXs9RyHDJjckNE6lZbY7pLYc+OpaZ2ase+MDEaTHc6YG3g4sa2Da+a2olMLcehACY3RKRuu3Pr36W4nWQwtVM79oWJWip6q+U4FMDkhojU7XyZvO08GfvCRC0VvdVyHApgckNE6nZnnLztPBn7wkQtFb3VchwKYHJDROrWe7zpSSB7NL6mdmrHvjBRS0VvtRyHApjcEJG6+fmbHnG2J3mid6zxwr4wUUtFb7UchwKY3BCR+qW+CaRMrn/XQuNr2u5Na7uwL0zUUtFbLcchMy7iR0Teg6vy3sS+MFHLyr5qOQ47WBXcDiY3REREnocrFBMREZHXYnJDREREqsKq4EQi84JxdIeJ0BeizFMRoS+IBMbkhkhUXlLp1yEi9IW1StqbXnN9JW0R+oJIcByWIhIRK/3eJEJfiFJJW4S+IPIATG6IRMNKvzeJ0BeiVNIWoS+IPASTGyLRsNLvTSL0hSiVtEXoCyIPweSGSDSs9HuTCH0hSiVtEfqCyEMwuSESDSv93iRCX4hSSVuEviDyEExuiETDSr83idAXolTSFqEviDwEkxsi0bDS700i9IUolbRF6AsiD8HkhkhErPR7kwh9IUolbRH6gsgDsHAmkci4Eu1NIvQFVygmchtWBbeDyQ0REZHnYVVwIiIi8lpMboiIiEhVWDiTiJQnyhyRpsYhynEQkV1MbohIWaJUsW5qHKIcBxE1iMNSRKQcUapYNzUOUY6DiBzC5IaIlCFKFeumxiHKcRCRw5jcEJEyRKli3dQ4RDkOInIYkxsiUoYoVaybGocox0FEDmNyQ0TKEKWKdVPjEOU4iMhhTG6ISBmiVLFuahyiHAcROYzJDREpQ5Qq1k2NQ5TjICKHMbkhIuWIUsW6qXGIchxE5BAWziQi5Ymysi9XKCbyWM58f3OFYiJSno8voOvv7iiaHocox0FEdnFYioiIiFSFyQ0RERGpCoeliJTEORomcvQD+1J9eE5JIW5NbjIzM7F69Wr89NNPCAoKQkpKChYuXIiOHTvafE9BQQEGDx5cb3tJSQni4+OVDJfIOawibSJHP7Av1YfnlBTk1mGpwsJCTJw4ETt37sTmzZtRW1uL1NRUXL58ucH3Hj58GHq93vzTvn17F0RM5CBWkTaRox/Yl+rDc0oKE+pR8F9//RWRkZEoLCzEgAEDrLapu3Nz/vx5tGjRwunP4KPgpDijAchKtFNsUWP6F+pLB9R9C16OfmBfqg/PKTWSM9/fQk0orqysBACEh4c32LZHjx7QarUYMmQIvv32W5vtqqurUVVVZfFDpChWkTaRox/Yl+rDc0ouIExyI0kSMjIycO+99yIxMdFmO61Wi5ycHOTn52P16tXo2LEjhgwZgi1btlhtn5mZibCwMPNPTEyMUodAZMIq0iZy9AP7Un14TskFhHlaatKkSfjxxx/x3Xff2W3XsWNHiwnHycnJOHnyJN555x2rQ1kzZsxARkaG+XVVVRUTHFIWq0ibyNEP7Ev14TklFxDizs2LL76ItWvX4ttvv0WbNm2cfn/fvn1x5MgRq78LCAhAaGioxQ+RolhF2kSOfmBfqg/PKbmAW5MbSZIwadIkrF69Gv/973+h0+katZ/9+/dDq9U23JDIFVhF2kSOfmBfqg/PKbmAW5ObiRMnIi8vD5999hlCQkJQXl6O8vJyXL161dxmxowZePbZZ82vs7Ky8OWXX+LIkSM4dOgQZsyYgfz8fEyaNMkdh0BkHatIm8jRD+xL9eE5JYW59VFwjcb6bcnly5dj9OjRAIDRo0ejrKwMBQUFAIC3334bOTk5OHXqFIKCgtC5c2fMmDEDaWlpDn0mHwUnl+IKrCZcoZis4TklJzjz/S3UOjeuwOSGiIjI83jsOjdERERETcXkhoiIiFRFmHVuiGTFsXyx1NYAu3OB82XAnXFA7/GAn7+7oyIilWJyQ+rDasNi2fQ6sON9QDLesu01IHkSkPqm++IiItXisBSpC6sNi2XT68D2JZaJDWB6vX2J6fdERDJjckPqYTSY7tjA2gOAN7ZteNXUjpRXW2O6Y2PPjqWmdkREMmJyQ+rBasNi2Z1b/47N7SSDqR0RkYyY3JB6sNqwWM6XyduOiMhBTG5IPVhtWCx3xsnbjojIQUxuSD1YbVgsvccDmgb+itH4mtoREcmIyQ2pB6sNi8XP3/S4tz3JE7neDRHJjskNqQurDYsl9U0gZXL9OzgaX9N2rnNDRApg4UxSJ65QLBauUExETeTM9zdXKCZ18vEFdP3dHQXV8fM3DUEREbkAh6WIiIhIVZjcEBERkapwWEpFDEYJu0rPoeLiNUSGBKKPLhy+PrYei6YGcd6OfNiXZA2vC1IIkxuV2HBQj7nriqGvvGbepg0LxJwRCRiWqLXzTrKKlcXlw74ka3hdkII4LKUCGw7q8ULePovEBgDKK6/hhbx92HBQ76bIPBQri8uHfUnW8LoghTG58XAGo4S564rt1cHG3HXFMBi96on/xmNlcfmwL8kaXhfkAkxuPNyu0nP17tjcSgKgr7yGXaXnXBeUJ2NlcfmwL8kaXhfkAkxuPFzFRduJTWPaeT1WFpcP+5Ks4XVBLsDkxsNFhgTK2s7rsbK4fNiXZA2vC3IBJjcero8uHNqwQHt1sKENMz0WTg5gZXH5sC/JGl4X5AJMbjycr48Gc0YkALBZBxtzRiRwvRtHsbK4fNiXZA2vC3IBJjcqMCxRi+xneiIqzHLoKSosENnP9OQ6N85iZXH5sC/JGl4XpDBWBVcRrlAsM66eKh/2JVnD64Kc4Mz3N5MbIiIiEp4z398cliIiIiJVYXJDREREqsLCmUREnkaEuSoixEBkA5MbIiJPIkI1bRFiILKDw1JERJ5ChGraIsRA1AAmN0REnkCEatoixEDkACY3RESeQIRq2iLEQOQAJjdERJ5AhGraIsRA5AAmN0REnkCEatoixEDkACY3RESeQIRq2iLEQOQAJjdERJ5AhGraIsRA5AAmN0REnkKEatoixEDUABbOJCLyNCKsDixCDORVnPn+5grFRESexscX0PVnDEQ2cFiKiIiIVIXJDREREakKkxsiIiJSFSY3REREpCpMboiIiEhVmNwQERGRqjC5ISIiIlVhckNERESqwuSGiIiIVIXJDREREakKkxsiIiJSFSY3REREpCpMboiIiEhVmNwQERGRqjC5ISIiIlVhckNERESq4ufuAIiEZTQAx7cDl34BmrcCYlMAH193R0VERA1w652bzMxM9O7dGyEhIYiMjMSjjz6Kw4cPN/i+wsJC9OrVC4GBgbj77ruxbNkyF0RLXqV4LZCVCHzyEJA/1vTfrETTdiIiEppbk5vCwkJMnDgRO3fuxObNm1FbW4vU1FRcvnzZ5ntKS0uRlpaG/v37Y//+/Zg5cyYmT56M/Px8F0ZOqla8FvjXs0DVacvtVXrTdiY4RERC00iSJLk7iDq//vorIiMjUVhYiAEDBlhtM336dKxduxYlJSXmbenp6fjhhx+wY8eOBj+jqqoKYWFhqKysRGhoqGyxk0oYDaY7NLcnNmYaIDQaeOkAh6iIiFzIme9voSYUV1ZWAgDCw8NtttmxYwdSU1Mttg0dOhR79uzB9evX67Wvrq5GVVWVxQ+RTce320lsAEACqk6Z2hERkZCESW4kSUJGRgbuvfdeJCYm2mxXXl6OVq1aWWxr1aoVamtrcebMmXrtMzMzERYWZv6JiYmRPXZSkUu/yNuOiIhcTpjkZtKkSfjxxx/x+eefN9hWo9FYvK4bWbt9OwDMmDEDlZWV5p+TJ0/KEzCpU/NWDbdxph0REbmcEI+Cv/jii1i7di22bNmCNm3a2G0bFRWF8vJyi20VFRXw8/NDREREvfYBAQEICAiQNV5SsdgU05yaKj0Aa9PRbsy5iU1xdWREROQgt965kSQJkyZNwurVq/Hf//4XOp2uwfckJydj8+bNFts2bdqEpKQkNGvWTKlQyVv4+ALDFt54cfudwBuvhy3gZGIiIoG5NbmZOHEi8vLy8NlnnyEkJATl5eUoLy/H1atXzW1mzJiBZ5991vw6PT0dx48fR0ZGBkpKSvDRRx/hww8/xLRp09xxCKRGCQ8DT6wAQrWW20OjTdsTHnZPXERE5BC3PgpubY4MACxfvhyjR48GAIwePRplZWUoKCgw/76wsBBTp07FoUOHEB0djenTpyM9Pd2hz+Sj4OQwrlBMRCQMZ76/hVrnxhWY3BAREXkej13nhoiIiKipmNwQERGRqjC5ISIiIlVhckNERESqwuSGiIiIVIXJDREREakKkxsiIiJSFSY3REREpCpMboiIiEhVhKgK7kp1CzJXVVW5ORIiIiJyVN33tiOFFbwuubl48SIAICYmxs2REBERkbMuXryIsLAwu228rraU0WjE6dOnERISYrNwpyerqqpCTEwMTp48ydpZMmB/yod9KS/2p3zYl/JSqj8lScLFixcRHR0NHx/7s2q87s6Nj48P2rRp4+4wFBcaGsr/SWXE/pQP+1Je7E/5sC/lpUR/NnTHpg4nFBMREZGqMLkhIiIiVWFyozIBAQGYM2cOAgIC3B2KKrA/5cO+lBf7Uz7sS3mJ0J9eN6GYiIiI1I13boiIiEhVmNwQERGRqjC5ISIiIlVhckNERESqwuTGg2VmZkKj0eCll16y2aagoAAajabez08//eS6QAX1xhtv1OuXqKgou+8pLCxEr169EBgYiLvvvhvLli1zUbRic7YveV027NSpU3jmmWcQERGB4OBgdO/eHXv37rX7Hl6f1jnbl7w+bYuLi7PaNxMnTrT5Hndcl163QrFa7N69Gzk5OejatatD7Q8fPmyxUmTLli2VCs2jdO7cGV9//bX5ta+vr822paWlSEtLw/jx45GXl4dt27ZhwoQJaNmyJR577DFXhCs0Z/qyDq9L686fP49+/fph8ODB+OqrrxAZGYmjR4+iRYsWNt/D69O6xvRlHV6f9e3evRsGg8H8+uDBg3jggQfw+OOPW23vruuSyY0HunTpEp5++mnk5uZi3rx5Dr0nMjLSof+ZvY2fn1+Dd2vqLFu2DG3btkVWVhYAoFOnTtizZw/eeecdr/7yqONMX9bhdWndwoULERMTg+XLl5u3xcXF2X0Pr0/rGtOXdXh91nd7grdgwQLcc889GDhwoNX27rouOSzlgSZOnIgHH3wQ999/v8Pv6dGjB7RaLYYMGYJvv/1Wweg8y5EjRxAdHQ2dToff//73OHbsmM22O3bsQGpqqsW2oUOHYs+ePbh+/brSoQrPmb6sw+vSurVr1yIpKQmPP/44IiMj0aNHD+Tm5tp9D69P6xrTl3V4fdpXU1ODvLw8jBkzxmYhanddl0xuPMzKlSuxb98+ZGZmOtReq9UiJycH+fn5WL16NTp27IghQ4Zgy5YtCkcqvt/85jdYsWIFNm7ciNzcXJSXlyMlJQVnz5612r68vBytWrWy2NaqVSvU1tbizJkzrghZWM72Ja9L+44dO4bs7Gy0b98eGzduRHp6OiZPnowVK1bYfA+vT+sa05e8Ph3z5Zdf4sKFCxg9erTNNm67LiXyGCdOnJAiIyOloqIi87aBAwdKU6ZMcWo/Dz30kDRixAiZo/N8ly5dklq1aiUtWrTI6u/bt28vvfXWWxbbvvvuOwmApNfrXRGix2ioL63hdXlTs2bNpOTkZIttL774otS3b1+b7+H1aV1j+tIaXp/1paamSg899JDdNu66LnnnxoPs3bsXFRUV6NWrF/z8/ODn54fCwkIsWbIEfn5+FpO87Onbty+OHDmicLSe54477kCXLl1s9k1UVBTKy8sttlVUVMDPzw8RERGuCNFjNNSX1vC6vEmr1SIhIcFiW6dOnXDixAmb7+H1aV1j+tIaXp+Wjh8/jq+//hrjxo2z285d1yWTGw8yZMgQHDhwAEVFReafpKQkPP300ygqKnLo6RQA2L9/P7RarcLRep7q6mqUlJTY7Jvk5GRs3rzZYtumTZuQlJSEZs2auSJEj9FQX1rD6/Kmfv364fDhwxbbfv75Z8TGxtp8D69P6xrTl9bw+rS0fPlyREZG4sEHH7Tbzm3XpWL3hMglbh+WevXVV6VRo0aZX7/33nvSF198If3888/SwYMHpVdffVUCIOXn57shWrH86U9/kgoKCqRjx45JO3fulB566CEpJCREKisrkySpfl8eO3ZMCg4OlqZOnSoVFxdLH374odSsWTNp1apV7joEYTjbl7wu7du1a5fk5+cnzZ8/Xzpy5Ij0j3/8QwoODpby8vLMbXh9OqYxfcnr0z6DwSC1bdtWmj59er3fiXJdMrnxcLcnN88995w0cOBA8+uFCxdK99xzjxQYGCjdeeed0r333iv95z//cX2gAnryySclrVYrNWvWTIqOjpZGjhwpHTp0yPz72/tSkiSpoKBA6tGjh+Tv7y/FxcVJ2dnZLo5aTM72Ja/Lhq1bt05KTEyUAgICpPj4eCknJ8fi97w+HedsX/L6tG/jxo0SAOnw4cP1fifKdamRJElS7r4QERERkWtxzg0RERGpCpMbIiIiUhUmN0RERKQqTG6IiIhIVZjcEBERkaowuSEiIiJVYXJDREREqsLkhoiIiFSFyQ0ReZTRo0fj0Ucftfn7jz/+GC1atHBZPA2Ji4tDVlaWu8Mg8ipMboiIZCBaUkXkzZjcEBERkaowuSEih61atQpdunRBUFAQIiIicP/99+Py5cvm3y9fvhydOnVCYGAg4uPj8cEHH5h/V1ZWBo1Gg5UrVyIlJQWBgYHo3LkzCgoKzG0MBgPGjh0LnU6HoKAgdOzYEYsXL25y3OvWrUOvXr0QGBiIu+++G3PnzkVtba359xqNBn//+9/x29/+FsHBwWjfvj3Wrl1rsY+1a9eiffv2CAoKwuDBg/HJJ59Ao9HgwoULKCgowPPPP4/KykpoNBpoNBq88cYb5vdeuXIFY8aMQUhICNq2bYucnJwmHxMR2aF4aU4iUoXTp09Lfn5+0rvvviuVlpZKP/74o7R06VLp4sWLkiRJUk5OjqTVaqX8/Hzp2LFjUn5+vhQeHi59/PHHkiRJUmlpqQRAatOmjbRq1SqpuLhYGjdunBQSEiKdOXNGkiRJqqmpkWbPni3t2rVLOnbsmJSXlycFBwdL//znP81xPPfcc9IjjzxiM87ly5dLYWFh5tcbNmyQQkNDpY8//lg6evSotGnTJikuLk564403zG3q4vrss8+kI0eOSJMnT5aaN28unT171hx7s2bNpGnTpkk//fST9Pnnn0utW7eWAEjnz5+XqqurpaysLCk0NFTS6/WSXq8390tsbKwUHh4uLV26VDpy5IiUmZkp+fj4SCUlJbKcFyKqj8kNETlk7969EgCprKzM6u9jYmKkzz77zGLbm2++KSUnJ0uSdDO5WbBggfn3169fl9q0aSMtXLjQ5udOmDBBeuyxx8yvnU1u+vfvL7311lsWbT799FNJq9WaXwOQXnvtNfPrS5cuSRqNRvrqq68kSZKk6dOnS4mJiRb7mDVrljm5sfa5dWJjY6VnnnnG/NpoNEqRkZFSdna2zWMgoqbxc+NNIyLyIN26dcOQIUPQpUsXDB06FKmpqfjd736HO++8E7/++itOnjyJsWPHYvz48eb31NbWIiwszGI/ycnJ5j/7+fkhKSkJJSUl5m3Lli3D3//+dxw/fhxXr15FTU0Nunfv3ui49+7di927d2P+/PnmbQaDAdeuXcOVK1cQHBwMAOjatav593fccQdCQkJQUVEBADh8+DB69+5tsd8+ffo4HMOt+9ZoNIiKijLvm4jkx+SGiBzi6+uLzZs3Y/v27di0aRP++te/YtasWfj+++/NCUJubi5+85vf1HtfQzQaDQDgX//6F6ZOnYpFixYhOTkZISEh+Mtf/oLvv/++0XEbjUbMnTsXI0eOrPe7wMBA85+bNWtWLyaj0QgAkCTJHGMdSZIcjsHevolIfkxuiMhhGo0G/fr1Q79+/TB79mzExsbiiy++QEZGBlq3bo1jx47h6aeftruPnTt3YsCAAQBMd3b27t2LSZMmAQC2bt2KlJQUTJgwwdz+6NGjTYq5Z8+eOHz4MNq1a9fofcTHx2P9+vUW2/bs2WPx2t/fHwaDodGfQUTyYXJDRA75/vvv8c033yA1NRWRkZH4/vvv8euvv6JTp04AgDfeeAOTJ09GaGgohg8fjurqauzZswfnz59HRkaGeT9Lly5F+/bt0alTJ7z33ns4f/48xowZAwBo164dVqxYgY0bN0Kn0+HTTz/F7t27odPpGh337Nmz8dBDDyEmJgaPP/44fHx88OOPP+LAgQOYN2+eQ/v44x//iHfffRfTp0/H2LFjUVRUhI8//hjAzbtOcXFxuHTpEr755ht069YNwcHB5jtaRORafBSciBwSGhqKLVu2IC0tDR06dMBrr72GRYsWYfjw4QCAcePG4e9//zs+/vhjdOnSBQMHDsTHH39cLzFZsGABFi5ciG7dumHr1q1Ys2YN7rrrLgBAeno6Ro4ciSeffBK/+c1vcPbsWYu7OI0xdOhQ/Pvf/8bmzZvRu3dv9O3bF++++y5iY2Md3odOp8OqVauwevVqdO3aFdnZ2Zg1axYAICAgAACQkpKC9PR0PPnkk2jZsiXefvvtJsVNRI2nkZwZOCYiaqSysjLodDrs37+/SROERTF//nwsW7YMJ0+edHcoRHQbDksRETnggw8+QO/evREREYFt27bhL3/5i3muEBGJhckNEZEDjhw5gnnz5uHcuXNo27Yt/vSnP2HGjBnuDouIrOCwFBEREakKJxQTERGRqjC5ISIiIlVhckNERESqwuSGiIiIVIXJDREREakKkxsiIiJSFSY3REREpCpMboiIiEhV/h9Eh0OBc6l49AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')\n",
    "plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')\n",
    "plt.plot(test_point[0], test_point[1], 'bo', label='test_point')\n",
    "plt.xlabel('sepal length')\n",
    "plt.ylabel('sepal width')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### scikit-learn实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>#sk-container-id-1 {color: black;background-color: white;}#sk-container-id-1 pre{padding: 0;}#sk-container-id-1 div.sk-toggleable {background-color: white;}#sk-container-id-1 label.sk-toggleable__label {cursor: pointer;display: block;width: 100%;margin-bottom: 0;padding: 0.3em;box-sizing: border-box;text-align: center;}#sk-container-id-1 label.sk-toggleable__label-arrow:before {content: \"▸\";float: left;margin-right: 0.25em;color: #696969;}#sk-container-id-1 label.sk-toggleable__label-arrow:hover:before {color: black;}#sk-container-id-1 div.sk-estimator:hover label.sk-toggleable__label-arrow:before {color: black;}#sk-container-id-1 div.sk-toggleable__content {max-height: 0;max-width: 0;overflow: hidden;text-align: left;background-color: #f0f8ff;}#sk-container-id-1 div.sk-toggleable__content pre {margin: 0.2em;color: black;border-radius: 0.25em;background-color: #f0f8ff;}#sk-container-id-1 input.sk-toggleable__control:checked~div.sk-toggleable__content {max-height: 200px;max-width: 100%;overflow: auto;}#sk-container-id-1 input.sk-toggleable__control:checked~label.sk-toggleable__label-arrow:before {content: \"▾\";}#sk-container-id-1 div.sk-estimator input.sk-toggleable__control:checked~label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-1 div.sk-label input.sk-toggleable__control:checked~label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-1 input.sk-hidden--visually {border: 0;clip: rect(1px 1px 1px 1px);clip: rect(1px, 1px, 1px, 1px);height: 1px;margin: -1px;overflow: hidden;padding: 0;position: absolute;width: 1px;}#sk-container-id-1 div.sk-estimator {font-family: monospace;background-color: #f0f8ff;border: 1px dotted black;border-radius: 0.25em;box-sizing: border-box;margin-bottom: 0.5em;}#sk-container-id-1 div.sk-estimator:hover {background-color: #d4ebff;}#sk-container-id-1 div.sk-parallel-item::after {content: \"\";width: 100%;border-bottom: 1px solid gray;flex-grow: 1;}#sk-container-id-1 div.sk-label:hover label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-1 div.sk-serial::before {content: \"\";position: absolute;border-left: 1px solid gray;box-sizing: border-box;top: 0;bottom: 0;left: 50%;z-index: 0;}#sk-container-id-1 div.sk-serial {display: flex;flex-direction: column;align-items: center;background-color: white;padding-right: 0.2em;padding-left: 0.2em;position: relative;}#sk-container-id-1 div.sk-item {position: relative;z-index: 1;}#sk-container-id-1 div.sk-parallel {display: flex;align-items: stretch;justify-content: center;background-color: white;position: relative;}#sk-container-id-1 div.sk-item::before, #sk-container-id-1 div.sk-parallel-item::before {content: \"\";position: absolute;border-left: 1px solid gray;box-sizing: border-box;top: 0;bottom: 0;left: 50%;z-index: -1;}#sk-container-id-1 div.sk-parallel-item {display: flex;flex-direction: column;z-index: 1;position: relative;background-color: white;}#sk-container-id-1 div.sk-parallel-item:first-child::after {align-self: flex-end;width: 50%;}#sk-container-id-1 div.sk-parallel-item:last-child::after {align-self: flex-start;width: 50%;}#sk-container-id-1 div.sk-parallel-item:only-child::after {width: 0;}#sk-container-id-1 div.sk-dashed-wrapped {border: 1px dashed gray;margin: 0 0.4em 0.5em 0.4em;box-sizing: border-box;padding-bottom: 0.4em;background-color: white;}#sk-container-id-1 div.sk-label label {font-family: monospace;font-weight: bold;display: inline-block;line-height: 1.2em;}#sk-container-id-1 div.sk-label-container {text-align: center;}#sk-container-id-1 div.sk-container {/* jupyter's `normalize.less` sets `[hidden] { display: none; }` but bootstrap.min.css set `[hidden] { display: none !important; }` so we also need the `!important` here to be able to override the default hidden behavior on the sphinx rendered scikit-learn.org. See: https://github.com/scikit-learn/scikit-learn/issues/21755 */display: inline-block !important;position: relative;}#sk-container-id-1 div.sk-text-repr-fallback {display: none;}</style><div id=\"sk-container-id-1\" class=\"sk-top-container\"><div class=\"sk-text-repr-fallback\"><pre>KNeighborsClassifier()</pre><b>In a Jupyter environment, please rerun this cell to show the HTML representation or trust the notebook. <br />On GitHub, the HTML representation is unable to render, please try loading this page with nbviewer.org.</b></div><div class=\"sk-container\" hidden><div class=\"sk-item\"><div class=\"sk-estimator sk-toggleable\"><input class=\"sk-toggleable__control sk-hidden--visually\" id=\"sk-estimator-id-1\" type=\"checkbox\" checked><label for=\"sk-estimator-id-1\" class=\"sk-toggleable__label sk-toggleable__label-arrow\">KNeighborsClassifier</label><div class=\"sk-toggleable__content\"><pre>KNeighborsClassifier()</pre></div></div></div></div></div>"
      ],
      "text/plain": [
       "KNeighborsClassifier()"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk = KNeighborsClassifier()\n",
    "clf_sk.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf_sk.score(X_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### sklearn.neighbors.KNeighborsClassifier\n",
    "\n",
    "- n_neighbors: 临近点个数\n",
    "- p: 距离度量\n",
    "- algorithm: 近邻算法，可选{'auto', 'ball_tree', 'kd_tree', 'brute'}\n",
    "- weights: 确定近邻的权重"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### kd树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kd-tree每个结点中主要包含的数据结构如下\n",
    "class KdNode(object):\n",
    "    def __init__(self, dom_elt, split, left, right):\n",
    "        self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)\n",
    "        self.split = split  # 整数（进行分割维度的序号）\n",
    "        self.left = left  # 该结点分割超平面左子空间构成的kd-tree\n",
    "        self.right = right  # 该结点分割超平面右子空间构成的kd-tree\n",
    "\n",
    "\n",
    "class KdTree(object):\n",
    "    def __init__(self, data):\n",
    "        k = len(data[0])  # 数据维度\n",
    "\n",
    "        def CreateNode(split, data_set):  # 按第split维划分数据集exset创建KdNode\n",
    "            if not data_set:  # 数据集为空\n",
    "                return None\n",
    "            # key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较\n",
    "            # operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象中的序号\n",
    "            #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序\n",
    "            data_set.sort(key=lambda x: x[split])\n",
    "            split_pos = len(data_set) // 2  # //为Python中的整数除法\n",
    "            median = data_set[split_pos]  # 中位数分割点\n",
    "            split_next = (split + 1) % k  # cycle coordinates\n",
    "\n",
    "            # 递归的创建kd树\n",
    "            return KdNode(\n",
    "                median,\n",
    "                split,\n",
    "                CreateNode(split_next, data_set[:split_pos]),  # 创建左子树\n",
    "                CreateNode(split_next, data_set[split_pos + 1:]))  # 创建右子树\n",
    "\n",
    "        self.root = CreateNode(0, data)  # 从第0维分量开始构建kd树,返回根节点\n",
    "\n",
    "\n",
    "# KDTree的前序遍历\n",
    "def preorder(root):\n",
    "    print(root.dom_elt)\n",
    "    if root.left:  # 节点不为空\n",
    "        preorder(root.left)\n",
    "    if root.right:\n",
    "        preorder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 对构建好的kd树进行搜索，寻找与目标点最近的样本点：\n",
    "from math import sqrt\n",
    "from collections import namedtuple\n",
    "\n",
    "# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数\n",
    "result = namedtuple(\"Result_tuple\",\n",
    "                    \"nearest_point  nearest_dist  nodes_visited\")\n",
    "\n",
    "\n",
    "def find_nearest(tree, point):\n",
    "    k = len(point)  # 数据维度\n",
    "\n",
    "    def travel(kd_node, target, max_dist):\n",
    "        if kd_node is None:\n",
    "            return result([0] * k, float(\"inf\"),\n",
    "                          0)  # python中用float(\"inf\")和float(\"-inf\")表示正负无穷\n",
    "\n",
    "        nodes_visited = 1\n",
    "\n",
    "        s = kd_node.split  # 进行分割的维度\n",
    "        pivot = kd_node.dom_elt  # 进行分割的“轴”\n",
    "\n",
    "        if target[s] <= pivot[s]:  # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)\n",
    "            nearer_node = kd_node.left  # 下一个访问节点为左子树根节点\n",
    "            further_node = kd_node.right  # 同时记录下右子树\n",
    "        else:  # 目标离右子树更近\n",
    "            nearer_node = kd_node.right  # 下一个访问节点为右子树根节点\n",
    "            further_node = kd_node.left\n",
    "\n",
    "        temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域\n",
    "\n",
    "        nearest = temp1.nearest_point  # 以此叶结点作为“当前最近点”\n",
    "        dist = temp1.nearest_dist  # 更新最近距离\n",
    "\n",
    "        nodes_visited += temp1.nodes_visited\n",
    "\n",
    "        if dist < max_dist:\n",
    "            max_dist = dist  # 最近点将在以目标点为球心，max_dist为半径的超球体内\n",
    "\n",
    "        temp_dist = abs(pivot[s] - target[s])  # 第s维上目标点与分割超平面的距离\n",
    "        if max_dist < temp_dist:  # 判断超球体是否与超平面相交\n",
    "            return result(nearest, dist, nodes_visited)  # 不相交则可以直接返回，不用继续判断\n",
    "\n",
    "        #----------------------------------------------------------------------\n",
    "        # 计算目标点与分割点的欧氏距离\n",
    "        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))\n",
    "\n",
    "        if temp_dist < dist:  # 如果“更近”\n",
    "            nearest = pivot  # 更新最近点\n",
    "            dist = temp_dist  # 更新最近距离\n",
    "            max_dist = dist  # 更新超球体半径\n",
    "\n",
    "        # 检查另一个子结点对应的区域是否有更近的点\n",
    "        temp2 = travel(further_node, target, max_dist)\n",
    "\n",
    "        nodes_visited += temp2.nodes_visited\n",
    "        if temp2.nearest_dist < dist:  # 如果另一个子结点内存在更近距离\n",
    "            nearest = temp2.nearest_point  # 更新最近点\n",
    "            dist = temp2.nearest_dist  # 更新最近距离\n",
    "\n",
    "        return result(nearest, dist, nodes_visited)\n",
    "\n",
    "    return travel(tree.root, point, float(\"inf\"))  # 从根节点开始递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例3.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 2]\n",
      "[5, 4]\n",
      "[2, 3]\n",
      "[4, 7]\n",
      "[9, 6]\n",
      "[8, 1]\n"
     ]
    }
   ],
   "source": [
    "data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]\n",
    "kd = KdTree(data)\n",
    "preorder(kd.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import perf_counter\n",
    "from random import random\n",
    "\n",
    "# 产生一个k维随机向量，每维分量值在0~1之间\n",
    "def random_point(k):\n",
    "    return [random() for _ in range(k)]\n",
    " \n",
    "# 产生n个k维随机向量 \n",
    "def random_points(k, n):\n",
    "    return [random_point(k) for _ in range(n)]     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result_tuple(nearest_point=[2, 3], nearest_dist=1.8027756377319946, nodes_visited=4)\n"
     ]
    }
   ],
   "source": [
    "ret = find_nearest(kd, [3,4.5])\n",
    "print (ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time:  4.576283599999442 s\n",
      "Result_tuple(nearest_point=[0.10198800405708075, 0.4923249318573608, 0.797610804445524], nearest_dist=0.008280524531854998, nodes_visited=59)\n"
     ]
    }
   ],
   "source": [
    "N = 400000\n",
    "t0 = perf_counter()\n",
    "kd2 = KdTree(random_points(3, N))            # 构建包含四十万个3维空间样本点的kd树\n",
    "ret2 = find_nearest(kd2, [0.1,0.5,0.8])      # 四十万个样本点中寻找离目标最近的点\n",
    "t1 = perf_counter()\n",
    "print (\"time: \",t1-t0, \"s\")\n",
    "print (ret2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
